| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 345591 | 2021-01-07T15:47:23 Z | NhatMinh0208 | ICC (CEOI16_icc) | C++14 | 5 ms | 876 KB |
// 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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 2 ms | 876 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 3 ms | 876 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 5 ms | 876 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 4 ms | 876 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 4 ms | 876 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 4 ms | 876 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |