#include "plants.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
#define sz(x) ((int)(x).size())
int K, N;
const int nmax = 2e5 + 5;
namespace Queue {
int next[nmax];
int inside[nmax];
set<int> heads;
void insert(int node) {
heads.emplace(node);
inside[node] = 1;
next[node] = -1;
for(int i = (node + 1) % N, d = 1; i != node && d < K; d++, i = (i + 1) % N) {
if(inside[i]) {
if(heads.count(i))
heads.erase(i);
next[node] = i;
}
}
for(int i = (node - 1 + N) % N, d = 1; i != node && d < K; d++, i = (i - 1 + N) % N) {
if(inside[i]) {
heads.erase(node);
next[i] = node;
}
}
}
vector<int> prune() {
vector<int> rez;
for(auto x : heads)
rez.emplace_back(x), inside[x] = 0;
heads.clear();
for(auto x : rez)
if(next[x] != -1) heads.emplace(next[x]);
return rez;
}
}
vector<int> topsort;
#define left ofia
#define right goa
int left[nmax][18], jumpl[nmax][18];
int right[nmax][18], jumpr[nmax][18];
void init(int k__, std::vector<int> r) {
K = k__;
N = sz(r);
topsort.resize(N);
vector<int> erased(N, 0);
for(int i = 0; i < sz(r); i++)
if(r[i] == 0) erased[i] = 1, Queue::insert(i);
int color = 0;
while(sz(Queue::heads)) {
auto rem = Queue::prune();
//for(auto x : rem) cerr << x << ' ';
//cerr << '\n';
++color;
for(auto x : rem) topsort[x] = color;
for(auto x : rem) {
for(int i = (x - 1 + N) % N, d = 1; d < K; d++, i = (i - 1 + N) % N) {
if(erased[i]) continue;
r[i]--;
if(r[i] == 0) erased[i] = 1, Queue::insert(i);
}
}
}
for(int x = 0; x < sz(r); x++) {
int mn = -1;
jumpl[x][0] = 0;
for(int i = (x - 1 + N) % N, d = 1; d < K; d++, i = (i - 1 + N) % N) {
if(topsort[i] > topsort[x])
mn = (mn == -1? jumpl[x][0] = d, i : topsort[mn] < topsort[i]? mn : jumpl[x][0] = d, i);
}
left[x][0] = mn == -1? x : mn;
mn = -1;
jumpr[x][0] = 0;
for(int i = (x + 1 + N) % N, d = 1; d < K; d++, i = (i + 1 + N) % N) {
if(topsort[i] > topsort[x])
mn = (mn == -1? jumpr[x][0] = d, i : topsort[mn] < topsort[i]? mn : jumpr[x][0] = d, i);
}
right[x][0] = mn == -1? x : mn;
//cerr << x << ": " << left[x][0] << ' ' << right[x][0] << '\t' << jumpl[x][0] << ' ' << jumpr[x][0] << '\n';
}
for(int step = 1; step < 18; step++)
for(int i = 0; i < N; i++)
left[i][step] = left[left[i][step - 1]][step - 1], jumpl[i][step] = jumpl[i][step - 1] + jumpl[left[i][step - 1]][step - 1],
right[i][step] = right[right[i][step - 1]][step - 1], jumpr[i][step] = jumpr[i][step - 1] + jumpr[right[i][step - 1]][step - 1];
//for(auto x : topsort) cerr << x << ' ';
//cerr << '\n';
return;
}
bool compare_smaller(int x, int y) {
//cerr << x << " vs " << y << '\n';
auto rdist = [&](int d) {
return d < x? N - x + d : d - x;
};
auto ldist = [&](int d) {
return d <= x? x - d : x + N - d;
};
int st = x, buffer = rdist(y);
for(int i = 17; i >= 0; i--) {
if(buffer < jumpr[st][i]) continue;
buffer -= jumpr[st][i];
st = right[st][i];
}
//cerr << "rightmost: " << x << ' ' << st << ' ' << y << "\t\t" << rdist(y) << ' ' << rdist(st) << ' ' << topsort[st] << ' ' << topsort[x] << '\n';
//for(int i = 0; i < N; i++) cerr << ldist(i) << ' ';
//cerr << '\n';
if(st == y) return 1;
if(rdist(y) - rdist(st) < K && topsort[y] > topsort[st]) return 1;
st = x;
buffer = ldist(y);
for(int i = 17; i >= 0; i--) {
if(buffer < jumpl[st][i]) continue;
buffer -= jumpl[st][i];
st = left[st][i];
}
//cerr << "leftmost: " << x << ' ' << st << ' ' << y << "\t\t" << ldist(y) << ' ' << ldist(st) << ' ' << topsort[st] << ' ' << topsort[x] << '\n';
if(st == y) return 1;
if(ldist(y) - ldist(st) < K && topsort[y] > topsort[st]) return 1;
return 0;
}
int compare_plants(int x, int y) {
//cerr << x << ' ' << y << '\t' << compare_smaller(x, y) << '\t' << compare_smaller(y, x) << '\n';
return topsort[x] > topsort[y]? -1 : 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
