Submission #603402

#	Time	Username	Problem	Language	Result	Execution time	Memory
603402		rrrr10000	Comparing Plants (IOI20_plants)	C++14	11 / 100	4107 ms	2097152 KiB

plants

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define pb emplace_back
#define fi first
#define se second
template<class T> void out(T a){cout<<a<<endl;}

vvb ans;
vi num;

void init(int k,vector<int> v){
    ll n=v.size();
    ans=vvb(n,vb(n,false));
    vvi g(n);
    vb done(n,false);
    vi cnt(n);
    set<ll> S;
    auto dif=[&](ll x){
        if(x>=0)return x;
        return x+n;
    };
    auto add=[&](ll i){
        auto itr=S.insert(i).fi;
        if(S.size()==1)return;
        if(itr==S.begin())itr=S.end();
        itr--;
        if(dif(i-(*itr))<k){
            g[*itr].pb(i);cnt[i]++;
        }
        itr++;
        if(itr==S.end())itr=S.begin();
        itr++;
        if(itr==S.end())itr=S.begin();
        if(dif((*itr)-i)<k){
            g[i].pb(*itr);cnt[*itr]++;
        }
    };
    rep(i,n)if(v[i]==0){
        add(i);
    }
    num=vi(n);
    rep(i,n){
        rep(j,n)if(!done[j]&&v[j]==0&&cnt[j]==0){
            num[j]=i;
            S.erase(j);
            done[j]=true;
            for(ll x:g[j])cnt[x]--;
            rep(t,k-1){
                ll nt=(j+t+1)%n;
                if(done[nt])continue;
                g[j].pb(nt);
            }
            rep(t,k-1){
                ll nt=dif(j-t-1);
                if(done[nt])continue;
                v[nt]--;
                g[j].pb(nt);
                if(v[nt]==0)add(nt);
            }
            break;
        }
    }
    g=vvi(n);
    rep(i,n)rep(j,k-1){
        ll t=(i+1+j+n)%n;
        if(num[i]<num[t])g[i].pb(t);
        else g[t].pb(i);
    }
    rep(i,n){
        queue<ll> que;
        que.push(i);ans[i][i]=true;
        while(!que.empty()){
            ll t=que.front();que.pop();
            for(ll x:g[t])if(!ans[i][x]){
                ans[i][x]=true;que.push(x);
            }
        }
    }
    // rep(i,n)for(ll j:g[i])cout<<i<<' '<<j<<endl;
}
int compare_plants(int x,int y){
    if(ans[x][y])return 1;
    if(ans[y][x])return -1;
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25