#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#define ll long long
//#define int ll
#define ull unsigned ll
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define chkmin(a,b) (a=min(a,b))
#define chkmax(a,b) (a=max(a,b))
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif
namespace {
const int maxn=505;
vector<int> adj[maxn*2];
bool vis[maxn*2];
mt19937 rng(49);
vector<int> gen(vector<int>& vec, int l, int r){
vector<int> res;
rep2(i,l,r+1) res.pb(vec[i]);
return res;
}
int query(vector<int> vec){
for(auto& i: vec) i++;
return Query(vec);
}
bool good(vector<int> vec){
return query(vec)==sz(vec);
}
} // namespace
void Solve(signed n) {
vector<int> ord;
set<pii> st;
rep1(_,10){
ord.clear();
rep(2*n) ord.pb(i);
shuffle(all(ord),rng);
vector<int> vec;
memset(vis,0,sizeof vis);
for(auto i: ord){
bool flag=1;
for(auto j: adj[i]) if(vis[j]) flag=0;
if(!flag) continue;
int l=0;
flag=1;
while(1){
vector<int> tmp=gen(vec,l,sz(vec)-1);
tmp.pb(i);
if(good(tmp)) break;
int r=sz(vec)-1;
while(l<r){
int mid=l+r>>1;
tmp=gen(vec,l,mid);
tmp.pb(i);
if(good(tmp)) l=mid+1;
else r=mid;
}
adj[vec[l]].pb(i),adj[i].pb(vec[l]);
st.insert({min(i,vec[l]),max(i,vec[l])});
l++;
flag=0;
if(l>=sz(vec)) break;
}
if(flag) vec.pb(i),vis[i]=1;
}
}
for(auto [x,y]: st) bug(x,y);
rep(2*n) bug(i,sz(adj[i]));
rep(2*n) if(sz(adj[i])==3){
if(query({i,adj[i][0],adj[i][1]})==1) st.erase({min(i,adj[i][2]),max(i,adj[i][2])}),bug(min(i,adj[i][2]),max(i,adj[i][2]));
else if(query({i,adj[i][0],adj[i][2]})==1) st.erase({min(i,adj[i][1]),max(i,adj[i][1])}),bug(min(i,adj[i][1]),max(i,adj[i][1]));
else st.erase({min(i,adj[i][0]),max(i,adj[i][0])}),bug(min(i,adj[i][0]),max(i,adj[i][0]));
}
assert(sz(st)==n);
for(auto [x,y]: st) Answer(x+1,y+1);
}
Compilation message
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:82:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | int mid=l+r>>1;
| ~^~
chameleon.cpp:32:18: warning: statement has no effect [-Wunused-value]
32 | #define bug(...) 777771449
| ^~~~~~~~~
chameleon.cpp:97:22: note: in expansion of macro 'bug'
97 | for(auto [x,y]: st) bug(x,y);
| ^~~
chameleon.cpp:97:11: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
97 | for(auto [x,y]: st) bug(x,y);
| ^~~~~
chameleon.cpp:32:18: warning: statement has no effect [-Wunused-value]
32 | #define bug(...) 777771449
| ^~~~~~~~~
chameleon.cpp:98:11: note: in expansion of macro 'bug'
98 | rep(2*n) bug(i,sz(adj[i]));
| ^~~
chameleon.cpp:100:125: warning: right operand of comma operator has no effect [-Wunused-value]
100 | if(query({i,adj[i][0],adj[i][1]})==1) st.erase({min(i,adj[i][2]),max(i,adj[i][2])}),bug(min(i,adj[i][2]),max(i,adj[i][2]));
| ^
chameleon.cpp:101:130: warning: right operand of comma operator has no effect [-Wunused-value]
101 | else if(query({i,adj[i][0],adj[i][2]})==1) st.erase({min(i,adj[i][1]),max(i,adj[i][1])}),bug(min(i,adj[i][1]),max(i,adj[i][1]));
| ^
chameleon.cpp:102:92: warning: right operand of comma operator has no effect [-Wunused-value]
102 | else st.erase({min(i,adj[i][0]),max(i,adj[i][0])}),bug(min(i,adj[i][0]),max(i,adj[i][0]));
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
35 ms |
464 KB |
Output is correct |
| 4 |
Correct |
33 ms |
464 KB |
Output is correct |
| 5 |
Correct |
36 ms |
464 KB |
Output is correct |
| 6 |
Correct |
36 ms |
460 KB |
Output is correct |
| 7 |
Correct |
37 ms |
480 KB |
Output is correct |
| 8 |
Correct |
39 ms |
444 KB |
Output is correct |
| 9 |
Correct |
37 ms |
464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Runtime error |
52 ms |
876 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
35 ms |
464 KB |
Output is correct |
| 4 |
Correct |
33 ms |
464 KB |
Output is correct |
| 5 |
Correct |
36 ms |
464 KB |
Output is correct |
| 6 |
Correct |
36 ms |
460 KB |
Output is correct |
| 7 |
Correct |
37 ms |
480 KB |
Output is correct |
| 8 |
Correct |
39 ms |
444 KB |
Output is correct |
| 9 |
Correct |
37 ms |
464 KB |
Output is correct |
| 10 |
Correct |
0 ms |
336 KB |
Output is correct |
| 11 |
Correct |
0 ms |
336 KB |
Output is correct |
| 12 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 13 |
Halted |
0 ms |
0 KB |
- |
