제출 #120564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120564		imyujin	자동 인형 (IOI18_doll)	C++14	100 / 100	138 ms	13672 KiB

doll

#include "doll.h"
#include<vector>

using namespace std;

#define MAXN 200000

int l[4*MAXN], r[4*MAXN], num[4*MAXN], numn=0;
bool chk[4*MAXN];

void create_circuit(int M, vector<int> A) {
	A.push_back(0);
	int N=A.size();
	vector<int> C(M+1, -1), X, Y;
	int two;
	int cnt=0;

	if(N==2){
		C[0]=A[0];
		C[A[0]]=0;
		answer(C, X, Y);
		return;
	}

	for(two=0; (1<<two)<N; two++);
	l[1]=0;
	r[1]=(1<<two)-1;
	for(int i=2; i<(1<<two+1); i++){
		if(i%2==0){
			l[i]=l[i/2];
			r[i]=(l[i/2]+r[i/2])/2;
		}
		else{
			l[i]=(l[i/2]+r[i/2])/2+1;
			r[i]=r[i/2];
		}
	}
	//for(int i=1; i<(1<<two); i++) printf("%d %d\n", l[i], r[i]);
	for(int i=1; i<(1<<two); i++){
		if(r[i]>=(1<<two)-N){
			num[i]=--numn;
			X.push_back(-1);
			Y.push_back(-1);
		}
		else num[i]=-1;
	}
	//for(int i=1; i<(1<<two); i++) printf("%d ", num[i]);
	for(int i=1; i<(1<<two-1); i++) if(r[i]>=(1<<two)-N&&l[i]<r[i]){
		X[-num[i]-1]=num[i*2];
		Y[-num[i]-1]=num[i*2+1];
	}
	for(int i=0; i<(1<<two); i++){
		int k;
		for(k=1; k<(1<<two)&&r[k]>=(1<<two)-N;){
			chk[k]=!chk[k];
			k=k*2+(chk[k]?0:1);
		}
		//printf("[%d]\n", k);
		if(r[k]>=(1<<two)-N){
			//printf("*");
			if(k%2==0) X[-num[k/2]-1]=A[cnt++];
			else Y[-num[k/2]-1]=A[cnt++];
		}
	}
	answer(C, X, Y);
}

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:28:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   28 |  for(int i=2; i<(1<<two+1); i++){
      |                     ~~~^~
doll.cpp:48:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   48 |  for(int i=1; i<(1<<two-1); i++) if(r[i]>=(1<<two)-N&&l[i]<r[i]){
      |                     ~~~^~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56