//#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;
vector<int> adj[1005];
int likes[1005];
int answered[1005];
void addedge(int u, int v){
//show2(u,v);
adj[u].push_back(v);
adj[v].push_back(u);
}
void answer(int u, int v){
//show3("ANS", u, v);
if(answered[u] or answered[v]) return;
answered[u] = 1;
answered[v] = 1;
Answer(u,v);
}
///claim: if A is an independent set, then A+v is independent iff query(A) < query(A+v)
vector<int> stuff[4];
vector<int> copy(vector<int> b){
vector<int> res(sz(b));
for(int i = 0;i < sz(b);i++) res[i] = b[i];
return res;
}
inline bool independent(vector<int> v, int u){
v.push_back(u);
return (sz(v)-1 < Query(v));
}
void Solve(int n){
for(int u = 1;u <= 2*n;u++){
int insertplace = -1;
int found = 0;
for(int j = 0;j < 4;j++){
if(stuff[j].empty()){
if(insertplace == -1) insertplace = j;
continue;
}
vector<int> v = copy(stuff[j]);
if(found == 3 or independent(v, u)){ ///is independent set
if(insertplace == -1) insertplace = j;
break;
}
while(true){
if(v.empty()) break;
if(independent(v, u)) break;
int low = -1, high = sz(v)-1;
while(low != high-1){
int mid = (low+high)/2;
vector<int> nv;
for(int i = 0;i <= mid;i++) nv.push_back(v[i]);
if(independent(nv, u)) low = mid;
else high = mid;
}
found++;
addedge(u, v[high]);
vector<int> ov;
for(int i = high+1;i < sz(v);i++) ov.push_back(v[i]);
swap(v,ov);
ov.clear();
}
}
//show2(u, insertplace);
stuff[insertplace].push_back(u);
}
///the last stuff;
for(int i = 1;i <= 2*n;i++){
//if(answered[i]) continue;
if(sz(adj[i]) == 1){
answer(i, adj[i][0]);
//show2(i, adj[i][0]);
}
else if(sz(adj[i]) == 3){
vector<int> &v = adj[i];
if(Query({i,v[0],v[1]}) == 1) likes[i] = v[2];
if(Query({i,v[2],v[1]}) == 1) likes[i] = v[0];
if(Query({i,v[0],v[2]}) == 1) likes[i] = v[1];
//show2(i, likes[i]);
}
else assert(false);
}
for(int i = 1;i <= 2*n;i++){
if(answered[i]) continue;
for(int x : adj[i]){
if(likes[x] != i and likes[i] != x) answer(i,x);
}
}
}
Compilation message
chameleon.cpp: In function 'void answer(int, int)':
chameleon.cpp:28:2: error: 'Answer' was not declared in this scope; did you mean 'answer'?
28 | Answer(u,v);
| ^~~~~~
| answer
chameleon.cpp: In function 'bool independent(std::vector<int>, int)':
chameleon.cpp:43:20: error: 'Query' was not declared in this scope
43 | return (sz(v)-1 < Query(v));
| ^~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:100:7: error: 'Query' was not declared in this scope
100 | if(Query({i,v[0],v[1]}) == 1) likes[i] = v[2];
| ^~~~~
chameleon.cpp:101:7: error: 'Query' was not declared in this scope
101 | if(Query({i,v[2],v[1]}) == 1) likes[i] = v[0];
| ^~~~~
chameleon.cpp:102:7: error: 'Query' was not declared in this scope
102 | if(Query({i,v[0],v[2]}) == 1) likes[i] = v[1];
| ^~~~~
