Submission #1213709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213709		hengliao	Comparing Plants (IOI20_plants)	C++20	11 / 100	4099 ms	193656 KiB

plants

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

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef int ll;

namespace{
    const ll mxN=5005; // warning

    ll n, k;
    vll adj[mxN];
    ll ans[mxN][mxN];
    bool done[mxN];
    ll val[mxN];
    bool visited[mxN];

    void dfs(ll cur){
        if(visited[cur]) return;
        visited[cur]=1;
        for(auto &it:adj[cur]){
            dfs(it);
        }
    }
}

void init(int K, vector<int> a) {
	memset(done, 0, sizeof(done));
    memset(ans, 0, sizeof(ans));
    n=a.size();
    k=K;
    auto update=[&](ll lef, ll rig, ll val){
        for(ll i=lef;i<=rig;i++){
            a[i]+=val;
        }
    };
    // if(2*k>n){
        
    //     for(ll i=n-1;i>=0;i--){
    //         vll tep;
    //         for(ll j=0;j<n;j++){
    //             if(!done[j] && a[j]==0){
    //                 tep.pb(j);
    //             }
    //         }
    //         ll dumb=0;
    //         if((ll) tep.size()==1){
    //             dumb=tep[0];
    //         }
    //         else{
    //             for(ll j=0;j<(ll) tep.size();j++){
    //                 ll pre=(j-1+(ll) tep.size())%((ll) tep.size());
    //                 if(((tep[j]-tep[pre]+n)%n)>=k){
    //                     dumb=tep[j];
    //                     break;
    //                 }
    //             }
    //         }
            
    //         val[dumb]=i;
    //         done[dumb]=1;
    //         ll lef=(dumb-k+1+n)%n;
    //         ll rig=(dumb-1+n)%n;
    //         if(lef>rig){
    //             update(lef, n-1, -1);
    //             update(0, rig, -1); 
    //         }    
    //         else{
    //             update(lef, rig, -1);
    //         }
    //     }
    //     return;
    //     // for(ll i=0;i<n;i++){
    //     //     cout<<val[i]<<' ';
    //     // }
    //     // cout<<'\n';
    // }
    auto check=[&](ll tar){
        if(a[tar]>0) return false;
        if(done[tar]) return false;
        ll cur=tar;
        for(ll i=0;i<k-1;i++){
            cur--;
            if(cur<0) cur+=n;
            if(done[cur]) continue;
            if(a[cur]==0) return false;
        }
        return true;
    };
    for(ll rep=0;rep<n;rep++){
        ll cur=-1;
        for(ll tar=0;tar<n;tar++){
            if(check(tar)){
                cur=tar;
                break;
            }
        }
        done[cur]=1;
        for(ll i=1;i<k;i++){
            ll cur2=(cur+i)%n;
            if(done[cur2]) continue;
            adj[cur].pb(cur2);
        }
        for(ll i=1;i<k;i++){
            ll cur2=(cur-i+n)%n;
            if(done[cur2]) continue;
            a[cur2]--;
            adj[cur].pb(cur2);
        }
    }
    for(ll i=0;i<n;i++){
        memset(visited, 0, sizeof(visited));
        dfs(i);
        for(ll j=0;j<n;j++){
            if(visited[j]){
                ans[i][j]=1;
                ans[j][i]=-1;
            }
        }
    }
}

int compare_plants(int x, int y) {
	// if(2*k>n){
    //     if(val[x]>val[y]) return 1;
    //     return -1;
    // }
    return (int) ans[x][y];
}

• 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