oj.uz

답안 #345599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
345599 2021-01-07T15:52:15 Z NhatMinh0208 CEOI16_icc (CEOI16_icc) C++14
0 / 100
 2000 ms 620 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)) 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;
		
		for (i=0;i<=N-t;i++)
		{
			assert(buc[alive[i]].size()>=1);
		}
		assert(alive.size()==N-t+1);
		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

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:124:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |    for (i=0;i<buc[cb].size();i++)
      |             ~^~~~~~~~~~~~~~~
icc.cpp:147:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |    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;
      |                      ^~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2036 ms 492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2040 ms 492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2068 ms 492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2075 ms 492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2063 ms 492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2027 ms 620 KB Time limit exceeded
2 Halted 0 ms 0 KB -