제출 #543019

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

doll

//implementation idea by TadijaSebez
#include "doll.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=200050;
const int M=2*N;
int n,d,root,ls[M],rs[M],tsz,id[M],p[M];
bool was[M];
int val(int x){
	x--;
	int ret=0;
	for(int i=0;i<25;i++)if(x>>i&1)ret+=(1<<(25-i));
	return ret;
}
void Build(int&c,int ss,int se){
	if(se<=d){c=root;return;}
	if(ss==se){c=-id[ss];return;}
	c=++tsz;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}
void create_circuit(int M,vector<int> A){
	A.pb(0);
	n=A.size();
	int sz=1;
	while(sz<n)sz*=2;
	d=sz-n;
	vector<int> ids;
	for(int i=1;i<=sz;i++)ids.pb(i);
	sort(ids.begin(),ids.end(),[&](int i,int j){return val(i)<val(j);});
	for(int i=d;i<sz;i++)was[ids[i]]=true,p[ids[i]]=i+1;
	for(int i=1,ptr=0;i<=sz;i++)if(was[i])id[p[i]]=A[ptr++];
	Build(root,1,sz);
	vector<int> C,X,Y;
	for(int i=0;i<=M;i++)C.pb(-1);
	for(int i=1;i<=tsz;i++)X.pb(-ls[i]),Y.pb(-rs[i]);
	answer(C,X,Y);
}

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

doll.cpp: In function 'void Build(int&, int, int)':
doll.cpp:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  int mid=ss+se>>1;
      |          ~~^~~

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