Submission #30687

#TimeUsernameProblemLanguageResultExecution timeMemory
30687zscoderICC (CEOI16_icc)C++14
100 / 100
166 ms2096 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include "icc.h" using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<int,ll> ii; typedef vector<int> vi; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<ll>::iterator sit; typedef map<ll,ll>::iterator mit; static int par[111]; static vi ilab[111]; static int lab[111]; static void init(int N) { for(int i = 0; i < N; i++) { par[i]=i; } } static int rt(int u) { if(par[u]==u) return u; else { assert(par[u]<=u); return (par[u]=rt(par[u])); } } static void merge(int u, int v) { u=rt(u); v=rt(v); if(u==v) return ; if(u>v) swap(u,v); par[v]=u; } int relabel(int N) { bool used[111]; memset(used,0,sizeof(used)); int cnt=0; for(int i = 0; i < N; i++) { //cerr<<i<<' '<<par[i]<<'\n'; par[i]=rt(i); ilab[i].clear(); if(!used[par[i]]) { assert(par[i]==i); lab[par[i]]=cnt; ilab[cnt].pb(i); cnt++; used[par[i]]=1; } else { lab[i]=lab[par[i]]; ilab[lab[i]].pb(i); } } return cnt; } static bool ask(vi &l, vi &r) { if(l.empty()||r.empty()) return 0; int L[l.size()]; int R[r.size()]; for(int i=0;i<l.size();i++) { L[i]=l[i]+1; //cerr<<l[i]<<' '; } //cerr<<'\n'; for(int i=0;i<r.size();i++) { R[i]=r[i]+1; //cerr<<r[i]<<' '; } //cerr<<'\n'; bool tmp = query(l.size(),r.size(),L,R); //cerr<<"RES : "<<tmp<<'\n'; return tmp; } void run(int N) { init(N); for(int i = 0; i < N - 1; i++) { int mx = relabel(N); int z = 0; while((1<<z)<mx) { z++; } int xr = 0; for(int i = 0; i < z; i++) { vi l,r; for(int j = 0; j < mx; j++) { if(j&(1<<i)) { for(int k = 0; k < ilab[j].size(); k++) { l.pb(ilab[j][k]); } } else { for(int k = 0; k < ilab[j].size(); k++) { r.pb(ilab[j][k]); } } } if(ask(l,r)) { xr^=(1<<i); } } int a = 0; int b = 0; int s = 0; for(int i=0;i<z;i++) { if((xr&(1<<i))) { s=i; break; } } a=(1<<s); int mask = (1<<s); for(int i = 0; i < z; i++) { if(i!=s) { vi L,R; for(int j = 0; j < mx; j++) { if((j&mask)==a&&(j&(1<<i))) { for(int k=0;k<ilab[j].size();k++) { L.pb(ilab[j][k]); } } } for(int j = 0; j < mx; j++) { if((j&mask)==b) { if(xr&(1<<i)) { if(!(j&(1<<i))) { for(int k=0;k<ilab[j].size();k++) { R.pb(ilab[j][k]); } } } else { if((j&(1<<i))) { for(int k=0;k<ilab[j].size();k++) { R.pb(ilab[j][k]); } } } } } if(ask(L,R)) { a^=(1<<i); if(!(xr&(1<<i))) b^=(1<<i); } else { if((xr&(1<<i))) b^=(1<<i); } mask^=(1<<i); } } //CC a and CC b are connected vi le,ri; for(int i=0;i<N;i++) { if(lab[par[i]]==a) le.pb(i); if(lab[par[i]]==b) ri.pb(i); } /* cerr<<"L : "; for(int i=0;i<le.size();i++) cerr<<le[i]<<' '; cerr<<'\n'; cerr<<"R : "; for(int i=0;i<ri.size();i++) cerr<<ri[i]<<' '; cerr<<'\n'; */ int u,v; int lo = 0; int hi = int(le.size()) - 1; int ans = -1; while(lo<=hi) { if(ans!=-1) break; int mid = (lo+hi)>>1; if(lo==hi&&ans==-1) { ans=lo; break; } vi L,R; for(int i = lo; i <= mid; i++) { L.pb(le[i]); } for(int i = 0; i < ri.size(); i++) { R.pb(ri[i]); } if(ask(L,R)) { if(mid==lo) { ans=mid; } hi = mid; } else { lo = mid + 1; } } u = ans; lo = 0; hi = int(ri.size()) - 1; ans = -1; while(lo<=hi) { if(ans!=-1) break; int mid = (lo+hi)>>1; if(lo==hi&&ans==-1) { ans=lo; break; } vi L,R; for(int i = 0; i < le.size(); i++) { L.pb(le[i]); } for(int i = lo; i <= mid; i++) { R.pb(ri[i]); } if(ask(L,R)) { if(mid==lo) { ans=mid; } hi = mid; } else { lo = mid + 1; } } v=ans; //cerr<<"ANS : "<<le[u]<<' '<<ri[v]<<'\n'; setRoad(le[u]+1,1+ri[v]); merge(le[u],ri[v]); } }

Compilation message (stderr)

icc.cpp: In function 'bool ask(vi&, vi&)':
icc.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<l.size();i++) 
               ^
icc.cpp:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<r.size();i++) 
               ^
icc.cpp: In function 'void run(int)':
icc.cpp:123:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k = 0; k < ilab[j].size(); k++)
                       ^
icc.cpp:130:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k = 0; k < ilab[j].size(); k++)
                       ^
icc.cpp:163:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int k=0;k<ilab[j].size();k++)
                    ^
icc.cpp:177:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int k=0;k<ilab[j].size();k++)
                      ^
icc.cpp:187:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int k=0;k<ilab[j].size();k++)
                      ^
icc.cpp:239:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < ri.size(); i++)
                     ^
icc.cpp:269:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < le.size(); i++)
                     ^
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...