#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
namespace {
int _N;
vector<int> adjlist[1005];
int done[1005];
int qcount = 0;
int QMAX = 30000;
vector<int> v;
int BUCKETS = 4;
map<vector<int>, int> M;
} // namespace
int q(vector<int> p) {
sort(p.begin(),p.end());
if (M[p] != 0) return M[p];
if (++qcount > QMAX) assert(false);
return M[p] = Query(p);
}
int isin(int L, int R, int x){
vector<int> QQ;
for (int j = L; j <= R; j++){
QQ.push_back(j);
}
int q1 = q(QQ);
QQ.push_back(x);
int q2 = q(QQ);
return q1-q2+1;
}
int msb(int x){
int K = 31-__builtin_clz(x);
return 1<<K;
}
void search(int L, int R, int x){
int d = R-L+1;
if (d <= BUCKETS){
for (int k = L; k <= R; k++){
if (q({k,x})){
adjlist[k].push_back(x);
adjlist[x].push_back(k);
}
}
return;
}
int STEP = d/BUCKETS;
int l = L, r = l+STEP;
for (int i = 0; i < BUCKETS; i++){
if (isin(l,r,x)) search(l,r,x);
l = r+1; r = min(R,l+STEP);
}
}
int getadj(int x){
//printf("searching for %d\n",x);
search(1,_N,x);
}
bool cmp(int a, int b){
return adjlist[a].size() < adjlist[b].size();
}
void Solve(int N) {
_N = N;
memset(done,0,sizeof(done));
vector<ii> ans;
for (int i = N+1; i <= N*2; i++){
getadj(i);
if (adjlist[i].size() == 1 && !done[i]){
//printf("FOUND %d with %d\n",i,adjlist[i][0]);
ans.push_back({i,adjlist[i][0]});
done[i] = done[adjlist[i][0]] = 1;
}
}
for (int i = 1; i <= 2*N; i++){
//printf("%d %d\n",i,adjlist[i].size());
//assert(adjlist[i].size() == 1 || adjlist[i].size()==3);
if (adjlist[i].size() == 1 && !done[i]){
//printf("FOUND %d with %d\n",i,adjlist[i][0]);
ans.push_back({i,adjlist[i][0]});
done[i] = done[adjlist[i][0]] = 1;
}
}
//printf("used %d so far\n",qcount);
for (int x = 1; x <= N; x++){
if (done[x]) continue;
else{
//printf("settling %d\n",x);
sort(adjlist[x].begin(),adjlist[x].end(),cmp);
for (auto y : adjlist[x]){
if (y == adjlist[x].back() || adjlist[y].size() == 1){
ans.push_back({x,y});
done[x] = done[y] = 1;
break;
}
//printf("maybe %d %d\n",x,y);
int num1 = 0;
for (auto z : adjlist[y]){
if (z != x && q({x,y,z}) == 1){
num1++;
}
}
if (num1 == 0) continue;
for (auto w : adjlist[x]){
if (w != y && q({x,y,w}) == 1){
num1++;
}
}
//printf("%d %d -> %d\n",x,y,num1);
if (num1 == 2){
ans.push_back({x,y});
done[x] = done[y] = 1;
break;
}
}
}
}
assert((int)ans.size() == N);
for (auto x : ans){
//printf("%d %d\n",x.first,x.second);
Answer(x.first,x.second);
}
}
Compilation message
chameleon.cpp: In function 'int getadj(int)':
chameleon.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
56 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
725 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
778 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
778 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
731 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
725 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
