#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
const int mx = 200005;
int k;
vi r;
int n;
pi rangs[mx][2];
void doK2Init(){
int start = 0;
for(int i = 0; i < n; i++){
if(r[i] != r[0]){
start = i;
break;
}
}
int cur = start;
while(true){
int end_ind = cur;
while(r[(end_ind+1) % n] == r[cur]){
end_ind = (end_ind+1) % n;
}
pi interval = mp(cur, (end_ind+1) % n);
// cout << cur << " " << end_ind << "\n";
// cout << interval.f << " " << interval.s << "\n";
for(int i = cur; ; (i = (i+1) % n)){
if(i == cur){
rangs[i][1] = mp(r[cur], interval.s);
}
else if(i == (end_ind+1) % n){
rangs[i][0] = mp(r[cur], interval.f);
break;
}
else{
rangs[i][0] = mp(r[cur], interval.f);
rangs[i][1] = mp(r[cur], interval.s);
}
}
cur = (end_ind+1) % n;
if(cur == start) break;
}
return;
}
int val[mx];
void init(int _k, vi _r) {
k = _k;
r = _r;
n = sz(r);
if(k == 2){
doK2Init();
return;
}
for(int i = 0; i < n; i++){
val[i] = -1;
}
for(int i = n-1; i >= 0; i--){
int cur_pos = -1;
for(int j = 0; j < n; j++){
if(val[j] != -1) continue;
if(r[j] == 0){
// cout << "j: " << j << "\n";
if(cur_pos == -1){
cur_pos = j;
}
else{
if((j-cur_pos)*2 > n){
cur_pos = j;
}
}
}
}
// cout << i << " " << cur_pos << "\n";
assert(cur_pos != -1);
val[cur_pos] = i;
for(int j = 0; j <= k-1; j++){
// cout << (cur_pos-j+n) % n << "\n";
r[(cur_pos-j+n) % n]--;
}
// for(int j = 0; j < n; j++){
// cout << "j, r[j]: " << j << " " << r[j] << "\n";
// }
}
}
bool isInInterval(int test, int int_beg, int int_end){
if(int_beg <= int_end){
return (int_beg <= test) && (test <= int_end);
}
return (int_beg <= test) || (test <= int_end);
}
int doK2Compare(int x, int y){
if(isInInterval(y, rangs[x][0].s, x)){
if(rangs[x][0].f == 1){
return 1;
}
else{
return -1;
}
}
else if(isInInterval(y, x, rangs[x][1].s)){
if(rangs[x][1].f == 1){
return -1;
}
else{
return 1;
}
}
return 0;
}
int compare_plants(int x, int y) {
if(k == 2){
return doK2Compare(x, y);
}
if(val[x] < val[y]) return -1;
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
56 ms |
3392 KB |
Output is correct |
7 |
Correct |
67 ms |
3996 KB |
Output is correct |
8 |
Correct |
98 ms |
8380 KB |
Output is correct |
9 |
Correct |
132 ms |
8388 KB |
Output is correct |
10 |
Correct |
92 ms |
8388 KB |
Output is correct |
11 |
Correct |
119 ms |
8376 KB |
Output is correct |
12 |
Correct |
89 ms |
8400 KB |
Output is correct |
13 |
Correct |
114 ms |
8380 KB |
Output is correct |
14 |
Correct |
90 ms |
8392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
11 ms |
332 KB |
Output is correct |
7 |
Correct |
290 ms |
4048 KB |
Output is correct |
8 |
Correct |
2 ms |
332 KB |
Output is correct |
9 |
Correct |
12 ms |
416 KB |
Output is correct |
10 |
Correct |
290 ms |
4064 KB |
Output is correct |
11 |
Correct |
188 ms |
3908 KB |
Output is correct |
12 |
Correct |
185 ms |
4136 KB |
Output is correct |
13 |
Correct |
328 ms |
4036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
11 ms |
332 KB |
Output is correct |
7 |
Correct |
290 ms |
4048 KB |
Output is correct |
8 |
Correct |
2 ms |
332 KB |
Output is correct |
9 |
Correct |
12 ms |
416 KB |
Output is correct |
10 |
Correct |
290 ms |
4064 KB |
Output is correct |
11 |
Correct |
188 ms |
3908 KB |
Output is correct |
12 |
Correct |
185 ms |
4136 KB |
Output is correct |
13 |
Correct |
328 ms |
4036 KB |
Output is correct |
14 |
Correct |
3060 ms |
4424 KB |
Output is correct |
15 |
Execution timed out |
4077 ms |
6852 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
56 ms |
3392 KB |
Output is correct |
7 |
Correct |
67 ms |
3996 KB |
Output is correct |
8 |
Correct |
98 ms |
8380 KB |
Output is correct |
9 |
Correct |
132 ms |
8388 KB |
Output is correct |
10 |
Correct |
92 ms |
8388 KB |
Output is correct |
11 |
Correct |
119 ms |
8376 KB |
Output is correct |
12 |
Correct |
89 ms |
8400 KB |
Output is correct |
13 |
Correct |
114 ms |
8380 KB |
Output is correct |
14 |
Correct |
90 ms |
8392 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
11 ms |
332 KB |
Output is correct |
21 |
Correct |
290 ms |
4048 KB |
Output is correct |
22 |
Correct |
2 ms |
332 KB |
Output is correct |
23 |
Correct |
12 ms |
416 KB |
Output is correct |
24 |
Correct |
290 ms |
4064 KB |
Output is correct |
25 |
Correct |
188 ms |
3908 KB |
Output is correct |
26 |
Correct |
185 ms |
4136 KB |
Output is correct |
27 |
Correct |
328 ms |
4036 KB |
Output is correct |
28 |
Correct |
3060 ms |
4424 KB |
Output is correct |
29 |
Execution timed out |
4077 ms |
6852 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |