Submission #1213748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213748		hengliao	Comparing Plants (IOI20_plants)	C++20	5 / 100	62 ms	29508 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=2e5+5; // warning

    ll n, k;
    vll adj[mxN];
    bool visited[mxN];
    ll dp[mxN][2];

    void dfs(ll cur){
        if(visited[cur]) return;
        visited[cur]=1;
        dp[cur][0]=cur;
        dp[cur][1]=cur;
        for(auto &it:adj[cur]){
            dfs(it);
            if(it==(cur+1)%n){
                dp[cur][0]=dp[it][0];
            }
            else{
                dp[cur][1]=dp[it][1];
            }
        }
    }
}

void init(int K, vector<int> a) {
    // memset(done, 0, sizeof(done));
    // memset(ans, 0, sizeof(ans));
    n=a.size();
    k=K;
    for(ll i=0;i<n;i++){
        ll nxt=(i+1)%n;
        if(a[i]==0){
            adj[i].pb(nxt);
        }
        else{
            adj[nxt].pb(i);
        }
    }
    
    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;
    // }
    if(y>x){
        if(dp[x][0]>=x){
            if(dp[x][0]>=y) return 1;
        }
        else{
            return 1;
        }
        if(dp[x][1]>x && dp[x][1]<=y){
            return 1;
        }
    }
    else{
        if(dp[x][0]<x && dp[x][0]>=y){
            return 1;
        }
        if(dp[x][1]<=x){
            if(dp[x][1]<=y) return 1;
        }
        else{
            return 1;
        }
    }
    if(x>y){
        if(dp[y][0]>=y){
            if(dp[y][0]>=x) return -1;
        }
        else{
            return -1;
        }
        if(dp[y][1]>y && dp[y][1]<=x){
            return -1;
        }
    }
    else{
        if(dp[y][0]<y && dp[y][0]>=x){
            return -1;
        }
        if(dp[y][1]<=y){
            if(dp[y][1]<=x) return -1;
        }
        else{
            return -1;
        }
    }
    return 0;
}

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