#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define endl '\n'
#define db double
#define ll __int128
//#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;
const int Max = 1e4 + 7, Inf = 1e9 + 7;
struct ABI
{
vector <int> tree;
void update(int i, int v)
{ i++;
for(i; i < (int) tree.size(); i += (i & -i))
tree[i] += v;
}
int sum(int i)
{
int ans = 0;
for(i; i > 0; i-= (i & -i))
ans += tree[i];
return ans;
}
int query(int l, int r)
{ l++; r++;
if(l <= 1) return sum(r);
else return sum(r) - sum(l-1);
}
ABI(int n)
{
tree.assign(n + 1, 0);
}
};
vector <vector<int>> v;
vector <int> pass;
void init(int k, std::vector<int> r)
{
int n = r.size(); k--;
pass.clear(); v.clear();
v.assign(n+1, vector <int> ());
pass.assign(n+1, 0);
_for(i, n) r[i] = k - r[i];
ABI St(2*n+7); vector <int> p(2*n+7);
bool can = true;
while (can)
{
can = false;
for(int i = 0; i < n; i++) if(p[i] == 0)
{
//cerr << i << " " << r[i] << " " << St.query(i, i+k) << endl;
if(k - St.query(i, i + k) == r[i]){
St.update(i, 1); St.update(i+n, 1);
p[i] = 1;
for(int j = i+1; j <= i+k; j++) if(p[j%n] == 0) {
v[i].push_back(j % n);
} else{
v[j % n].push_back(i);
}
can = true;
}
}
}
/*for(int i = 0; i < n; i++){
cerr << "I: " << i << " -> ";
for(auto& u : v[i]) {
cerr << u << " ";
}cerr << endl;
}*/
return;
}
int find(int node, int x){
if(node == x) return 1;
if(pass[node]) return 0;
pass[node] = 1;
int can = 0;
for(auto&u : v[node]){
can = can | find(u, x);
}
return can;
}
int cmp(int a, int b){
for(auto& u : pass) u = 0;
return find(a, b);
}
int compare_plants(int x, int y) {
if(cmp(x, y)) return 1;
if(cmp(y, x)) return -1;
return 0;
}
Compilation message
plants.cpp: In member function 'void ABI::update(int, int)':
plants.cpp:28:7: warning: statement has no effect [-Wunused-value]
28 | for(i; i < (int) tree.size(); i += (i & -i))
| ^
plants.cpp: In member function 'int ABI::sum(int)':
plants.cpp:35:7: warning: statement has no effect [-Wunused-value]
35 | for(i; i > 0; i-= (i & -i))
| ^
# |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
29 ms |
4188 KB |
Output is correct |
7 |
Incorrect |
618 ms |
6672 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 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 |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 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 |
344 KB |
Output is correct |
3 |
Incorrect |
1862 ms |
4956 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 |
352 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 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 |
0 ms |
348 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 |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
29 ms |
4188 KB |
Output is correct |
7 |
Incorrect |
618 ms |
6672 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |