IOI '20 - Plants (5pts)

#include "plants.h"

using namespace std;

int n;
vector<int> greater, less;

void init(int k, vector<int> r) {
    n = r.size();
    greater.resize(n);
    less.resize(n);

    // find cross-over
    int start = 0;
    while (r[(start-1+n)%n] == r[start]) ++start;

    int cur = (start-1+n)%n;
    do {
        int nxt = (cur+1)%n;
        if (r[cur]) less[cur] = less[nxt]+1;
        else greater[cur] = greater[nxt]+1;
        cur = (cur-1+n)%n;
    } while ((cur+1)%n != start);
    return;
}

int compare_plants(int x, int y) {
    int sub = (x < y ? 0 : n);
    if (x+greater[x]-sub >= y) return 1;
    if (x+less[x]-sub >= y) return -1;
    sub = n-sub;
    if (y+greater[y]-sub >= x) return -1;
    if (y+less[y]-sub >= x) return 1;
    return 0;
}