забор - Codechef апреля 2019 года долгое испытание - PullRequest
Новая
       6

забор - Codechef апреля 2019 года долгое испытание

0 голосов
/ 21 мая 2019

В следующем вопросе я получаю только 2 правильных ответа для приведенного ниже кода.Пожалуйста, помогите мне с тем, какие дела идут не так.растение встречается 2 ребра подсчитываются (как по строке, так и по столбцу), предыдущий проверяется на смежность в строке или столбце.Если смежные, 2 общих ребра вычитаются.

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

bool sortbysec(const pair<ll,ll> &a,const pair<ll,ll> &b) 
    { 
    return (a.second < b.second); 
    } 

int main() {

    ll t;
    cin>>t;
    while(t--){
        ll n,m,k;
        cin>>n>>m>>k;
        vector<pair<ll,ll>> a(k,make_pair(0,0));
        ll count=4;
        if(k==0) count=0;
        else{
            ll x,y;
            int l=1;
            cin>>x>>y;
            a[0]=make_pair(x,y);

            for(ll i=1;i<k;i++){
            ll x,y;
            cin>>x>>y;
            a[l]=make_pair(x,y);
            if(a[l]!=a[l-1]) l++;
            }

            sort(a.begin(),a.end());

            for(ll i=1;i<k;i++){

            if((a[i-1].first==a[i].first && a[i-1].second+1==a[i].second)) count-=2;
            count+=2;
            }

            sort(a.begin(),a.end(),sortbysec);

            for(ll i=1;i<k;i++){

            if((a[i-1].second==a[i].second && a[i-1].first+1==a[i].first)) count-=2;
            count+=2;
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

1 Ответ

0 голосов
/ 22 мая 2019

Вы не можете написать алгоритм, в котором вы строите сетку, он имеет как минимум сложность O (MN) и, как вы можете видеть в ограничениях NM <= 10 ^ 18, что невозможно. </p>

Вынужно написать алгоритм со сложностью O (K), потому что мы знаем количество растений K <= 10 ^ 5. </p>

Это можно сделать довольно легко:

  1. Создайте HashMap<Integer, HashSet<Integer>>, где вы вводите все значения растений.Цель состоит в том, чтобы запросить соседние ячейки в O (1).

  2. Затем для каждого растения вы добавляете 4 - adjacent plants к сумме ограждения.Например, если вы хотите проверить, есть ли у {3, 7000} растение слева, вы делаете map.containsKey(2) && map.get(2).contains(7000).Таким образом, вам даже не нужна специальная обработка растений на границе сетки.

...