Submission #552095

#TimeUsernameProblemLanguageResultExecution timeMemory
552095i_am_noobChameleon's Love (JOI20_chameleon)C++17
100 / 100
50 ms1612 KiB
#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],de[maxn*2][maxn*2]; int used=0; 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){ used++; 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(_,20){ int need=0; rep(2*n) rep1(j,i) if(sz(adj[i])<3&&sz(adj[j])<3&&!de[i][j]) need++; if(need<=18000-used) break; ord.clear(); rep(2*n){ bool flag=0; rep1(j,2*n) if(i!=j&&!de[i][j]) flag=1; if(flag&&sz(adj[i])<3) 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; for(auto j: vec) de[i][j]=de[j][i]=1; 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; } } rep(2*n) rep1(j,i) if(sz(adj[i])<3&&sz(adj[j])<3&&!de[i][j]){ if(query({i,j})==1){ adj[i].pb(j),adj[j].pb(i); st.insert({min(i,j),max(i,j)}); } } for(auto [x,y]: st) bug(x,y); rep(2*n) bug(i,sz(adj[i])); rep(2*n) assert(sz(adj[i])==1||sz(adj[i])==3); 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 (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:92:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |      int mid=l+r>>1;
      |              ~^~
chameleon.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define bug(...) 777771449
      |                  ^~~~~~~~~
chameleon.cpp:113:22: note: in expansion of macro 'bug'
  113 |  for(auto [x,y]: st) bug(x,y);
      |                      ^~~
chameleon.cpp:113:11: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  113 |  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:114:11: note: in expansion of macro 'bug'
  114 |  rep(2*n) bug(i,sz(adj[i]));
      |           ^~~
chameleon.cpp:117:125: warning: right operand of comma operator has no effect [-Wunused-value]
  117 |   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:118:130: warning: right operand of comma operator has no effect [-Wunused-value]
  118 |   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:119:92: warning: right operand of comma operator has no effect [-Wunused-value]
  119 |   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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...