oj.uz

답안 #345531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
345531 2021-01-07T14:34:31 Z NhatMinh0208 CEOI16_icc (CEOI16_icc) C++14
0 / 100
 6 ms 1004 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++)
	{
		assert(alive.size()==N-t+1);
		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)) 
				{
					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;
		
	//	assert((0<=ca)and(ca<=N-t));
	//	assert((0<=cb)and(cb<=N-t));
		ca=alive[ca];
		cb=alive[cb];
	//	assert(buc[ca].size()>=1);
	//	assert(buc[cb].size()>=1);
		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:41:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |   assert(alive.size()==N-t+1);
      |          ~~~~~~~~~~~~^~~~~~~
icc.cpp:120:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |    for (i=0;i<buc[cb].size();i++)
      |             ~^~~~~~~~~~~~~~~
icc.cpp:143:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |    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 Runtime error 3 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -