제출 #432636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432636		frodakcin	자동 인형 (IOI18_doll)	C++11	10 / 100	1 ms	284 KiB

doll

#include "doll.h"
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>

const int MN = 2e5;

int S;
std::vector<int> X, Y;
bool root[MN], state[MN];

void dfs(int &n, int l, int r, int qr)
{
	n=++S; X.push_back(0), Y.push_back(0);
	if(r-l>2)
	{
		int m=l+(r-l)/2;
		dfs(X[n-1], l, m, qr);
		if(m < qr) dfs(Y[n-1], m, r, qr);
	}
	else
		root[n]=1;
}

void create_circuit(int M, std::vector<int> A) {
	X.reserve(MN);
	Y.reserve(MN);

  int N = A.size();
  std::vector<int> C(M + 1);
	C[0]=A[0];
	if(N==1)
	{
		C[C[0]]=0;
		answer(C, X, Y);
		return;
	}

	for(int i=1;i<=M;++i)
		C[i]=-1;

	//for(auto x:A) printf("%d ", x); printf("\n");
	std::rotate(A.begin(), A.begin()+1, A.end());
	//for(auto x:A) printf("%d ", x); printf("\n");
	A.back()=0;
	if(A.size()&1)
		A.insert(A.begin(), -1);

	int d = 31 - __builtin_clz((int)A.size()-1);
	assert((1<<d+1) >= A.size() && A.size() > (1<<d));

	int top;
	dfs(top, 0, N, A.size());
	for(int& x:X) x*=-1;
	for(int& x:Y) x*=-1;

	int ctr=0;
	int n=-top;
	for(;n != 0;)
	{
		if(n > 0)
			n = -top;
		else if(root[-n])
		{
			state[-n] ^= 1;
			assert(ctr < A.size());
			n = (state[-n] ? X[-n-1] : Y[-n-1]) = A[ctr++];
		}
		else
		{
			state[-n] ^= 1;
			n = state[-n] ? X[-n-1] : Y[-n-1];
		}
	}
	//printf("%d %lu\n", ctr, A.size());
	assert(ctr == A.size());

  answer(C, X, Y);
}

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

In file included from /usr/include/c++/10/cassert:44,
                 from doll.cpp:3:
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:51:14: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   51 |  assert((1<<d+1) >= A.size() && A.size() > (1<<d));
      |             ~^~
doll.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  assert((1<<d+1) >= A.size() && A.size() > (1<<d));
      |         ~~~~~~~~~^~~~~~~~~~~
doll.cpp:51:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |  assert((1<<d+1) >= A.size() && A.size() > (1<<d));
      |                                 ~~~~~~~~~^~~~~~~~
doll.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    assert(ctr < A.size());
      |           ~~~~^~~~~~~~~~
doll.cpp:77:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  assert(ctr == A.size());
      |         ~~~~^~~~~~~~~~~

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