oj.uz

Submission #345605

# Submission time Handle Problem Language Result Execution time Memory
345605 2021-01-07T15:57:28 Z NhatMinh0208 ICC (CEOI16_icc) C++14
100 / 100
 171 ms 768 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 iter=0;
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++)
	{
	iter++;
	assert(iter<=2500);
		u=ceil(log2(N-t+1));
		mas=0;
		ca=0;
		cb=0;
		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)) for (int g : buc[alive[j]])
				{
					qa[sa]=g;
					sa++;
				}
				else for (int g : buc[alive[j]])
				{
					qb[sb]=g;
					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) for (int g : buc[alive[j]])
				{
					qa[sa]=g;
					sa++;
				}
				else  for (int g : buc[alive[j]])
				{
					qb[sb]=g;
					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;
		
		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;
				else l=mid+1;
		}
		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;
				else l=mid+1;
		}
		
		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

icc.cpp: In function 'int querySafe(int, int, int*, int*)':
icc.cpp:21:10: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
   21 |  if (!(sa*sb)) return 0;
      |       ~~~^~~~
icc.cpp: In function 'void run(int)':
icc.cpp:117:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |    for (i=0;i<buc[cb].size();i++)
      |             ~^~~~~~~~~~~~~~~
icc.cpp:140:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |    for (i=0;i<buc[ca].size();i++)
      |             ~^~~~~~~~~~~~~~~
icc.cpp:27:22: warning: unused variable 't1' [-Wunused-variable]
   27 |  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;
      |                      ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 492 KB Ok! 117 queries used.
2 Correct 9 ms 492 KB Ok! 115 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 492 KB Ok! 649 queries used.
2 Correct 48 ms 492 KB Ok! 540 queries used.
3 Correct 50 ms 492 KB Ok! 577 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 620 KB Ok! 1563 queries used.
2 Correct 157 ms 732 KB Ok! 1337 queries used.
3 Correct 166 ms 604 KB Ok! 1609 queries used.
4 Correct 166 ms 492 KB Ok! 1537 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 492 KB Ok! 1556 queries used.
2 Correct 168 ms 492 KB Ok! 1476 queries used.
3 Correct 158 ms 492 KB Ok! 1467 queries used.
4 Correct 169 ms 492 KB Ok! 1590 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 620 KB Ok! 1365 queries used.
2 Correct 158 ms 492 KB Ok! 1389 queries used.
3 Correct 162 ms 620 KB Ok! 1405 queries used.
4 Correct 156 ms 768 KB Ok! 1432 queries used.
5 Correct 171 ms 732 KB Ok! 1594 queries used.
6 Correct 168 ms 492 KB Ok! 1590 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 604 KB Ok! 1429 queries used.
2 Correct 160 ms 620 KB Ok! 1375 queries used.