#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
namespace {
int BKSZA = 50;
int BKSZB = 10;
int _N;
int adjmat[1005][1005];
vector<int> adjlist[1005];
int done[1005];
int qcount = 0;
int QMAX = 20000;
vector<int> v;
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;
}
int getadj(int x){
//printf("trying to find %d\n",x);
for (int i = 0; i <= _N/BKSZA; i++){
vector<int> QQ;
int l = BKSZA*i+1, r = min(_N,BKSZA*(i+1));
//printf("bucket %d %d %d\n",i,l,r);
if (isin(l,r,x)){
//printf("something is in bucket (%d,%d)\n",l,r);
for (int j = 0; j <= BKSZA/BKSZB; j++){
vector<int> QQ;
int L = l+BKSZB*j, R = min(_N,l+min(BKSZA,BKSZB*(j+1))-1);
//printf("minibucket %d %d %d\n",j,L,R);
if (L > _N || R > _N) break;
if (isin(L,R,x)){
//printf("something is in minibucket (%d,%d)\n",L,R);
for (int k = L; k <= R; k++){
if (q({k,x}) == 1){
//printf("found %d\n",k);
adjlist[k].push_back(x);
adjlist[x].push_back(k);
}
}
}
}
}
}
}
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){
//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);
for (auto y : adjlist[x]){
//printf("maybe %d %d\n",x,y);
int num1 = 0;
for (auto z : adjlist[y]){
if (z != x && q({x,y,z}) == 1){
num1++;
}
}
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:59:1: warning: no return statement in function returning non-void [-Wreturn-type]
59 | }
| ^
chameleon.cpp: At global scope:
chameleon.cpp:9:9: warning: '{anonymous}::adjmat' defined but not used [-Wunused-variable]
9 | int adjmat[1005][1005];
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
464 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
464 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
464 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
464 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
464 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
