Submission #345591

#TimeUsernameProblemLanguageResultExecution timeMemory
345591NhatMinh0208ICC (CEOI16_icc)C++14
0 / 100
5 ms876 KiB
// Problem : D - Binomial Coefficient is Fun // Contest : AtCoder - AtCoder Regular Contest 110(Sponsored by KAJIMA CORPORATION) // URL : https://atcoder.jp/contests/arc110/tasks/arc110_d // Memory Limit : 1024 MB // Time Limit : 2000 ms // Powered by CP Editor (https://github.com/cpeditor/cpeditor) /* Normie's Template v2.0 */ // Standard library in one include. #include <bits/stdc++.h> using namespace std; #include "icc.h" int querySafe(int sa, int sb, int qa[], int qb[]) { if (!(sa*sb)) return 0; return query(sa,sb,qa,qb); } void run(int N) { int i=0,j=0,k=0,t=0,t1=0,u=0,v=0,a=0,b=0,mas=0,ca=0,cb=0,l,r; int filter[32]; vector<int> buc[1001]; vector<int> alive; int qa[1001],qb[1001]; int sa=0,sb=0; for (i=1;i<=N;i++) { buc[i].push_back(i); alive.push_back(i); } for (t=1;t<N;t++) { u=ceil(log2(N-t+1)); mas=0; ca=0; cb=0; for (i=0;i<=N-t;i++) { assert(buc[alive[i]].size()>=1); } assert(alive.size()==N-t+1); for (i=0;i<u;i++) { filter[i]=-1; sa=0; sb=0; for (j=0;j<N-t+1;j++) { if (j&(1<<i)) { qa[sa]=alive[j]; sa++; } else { qb[sb]=alive[j]; sb++; } } v=querySafe(sa,sb,qa,qb); if (v) mas^=(1<<i); } for (i=0;i<u;i++) if (mas&(1<<i)) { filter[i]=0; break; } for (i=0;i<u;i++) if (filter[i]==-1) { filter[i]=0; sa=0; sb=0; for (j=0;j<N-t+1;j++) { int fail=0; for (k=0;k<u;k++) if ((filter[k]>=0)and((j&(1<<k))>>k!=filter[k])) fail=1; if (!fail) { qa[sa]=alive[j]; sa++; } else { qb[sb]=alive[j]; sb++; } } v=querySafe(sa,sb,qa,qb); if (v) ; else filter[i]=1; } for (i=0;i<u;i++) ca+=(1<<i)*filter[i]; cb=ca^mas; for (i=0;i<=N-t;i++) { assert(buc[alive[i]].size()>=1); } assert(alive.size()==N-t+1); assert(0<=ca); assert(ca<=N-t); assert(0<=cb); assert(cb<=N-t); ca=alive[ca]; cb=alive[cb]; l=0; r=buc[ca].size()-1; while(l<r) { int mid=(l+r)/2; sa=0; sb=0; for (i=l;i<mid;i++) { qa[sa]=buc[ca][i]; sa++; } for (i=0;i<buc[cb].size();i++) { qb[sb]=buc[cb][i]; sb++; } v=querySafe(sa,sb,qa,qb); if (v) r=mid-1; else l=mid; } a=buc[ca][l]; l=0; r=buc[cb].size()-1; while(l<r) { int mid=(l+r)/2; sa=0; sb=0; for (i=l;i<mid;i++) { qa[sa]=buc[cb][i]; sa++; } for (i=0;i<buc[ca].size();i++) { qb[sb]=buc[ca][i]; sb++; } v=querySafe(sa,sb,qa,qb); if (v) r=mid-1; else l=mid; } b=buc[cb][l]; setRoad(a,b); for (int g : buc[ca]) buc[cb].push_back(g); buc[ca].clear(); auto g=find(alive.begin(),alive.end(),ca); assert(g!=alive.end()); alive.erase(g); } }

Compilation message (stderr)

icc.cpp: In function 'int querySafe(int, int, int*, int*)':
icc.cpp:20:10: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
   20 |  if (!(sa*sb)) return 0;
      |       ~~~^~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from icc.cpp:14:
icc.cpp: In function 'void run(int)':
icc.cpp:49:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |   assert(alive.size()==N-t+1);
      |          ~~~~~~~~~~~~^~~~~~~
icc.cpp:108:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |   assert(alive.size()==N-t+1);
      |          ~~~~~~~~~~~~^~~~~~~
icc.cpp:128:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |    for (i=0;i<buc[cb].size();i++)
      |             ~^~~~~~~~~~~~~~~
icc.cpp:151:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |    for (i=0;i<buc[ca].size();i++)
      |             ~^~~~~~~~~~~~~~~
icc.cpp:26:22: warning: unused variable 't1' [-Wunused-variable]
   26 |  int i=0,j=0,k=0,t=0,t1=0,u=0,v=0,a=0,b=0,mas=0,ca=0,cb=0,l,r;
      |                      ^~
#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...