Submission #432654

#	Time	Username	Problem	Language	Result	Execution time	Memory
432654		frodakcin	Mechanical Doll (IOI18_doll)	C++11	12 / 100	97 ms	9344 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];

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

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());
	A.back()=0;
	if(A.size()&1)
		A.insert(A.begin(), -1);
	//for(auto x:A) printf("%d ", x); printf("\n");

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

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

	int ctr=0;
	int n=-top;
	for(;n != 0;)
	{
		//printf("ideal: %d\n", n);
		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);
}

Compilation message (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:52:14: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   52 |  assert((1<<d+1) >= A.size() && A.size() > (1<<d));
      |             ~^~
doll.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  assert((1<<d+1) >= A.size() && A.size() > (1<<d));
      |         ~~~~~~~~~^~~~~~~~~~~
doll.cpp:52:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |  assert((1<<d+1) >= A.size() && A.size() > (1<<d));
      |                                 ~~~~~~~~~^~~~~~~~
doll.cpp:55:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   55 |  top = dfs(0, 1<<d+1, (1<<d+1)-A.size());
      |                  ~^~
doll.cpp:55:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   55 |  top = dfs(0, 1<<d+1, (1<<d+1)-A.size());
      |                           ~^~
In file included from /usr/include/c++/10/cassert:44,
                 from doll.cpp:3:
doll.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    assert(ctr < A.size());
      |           ~~~~^~~~~~~~~~
doll.cpp:79:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  assert(ctr == A.size());
      |         ~~~~^~~~~~~~~~~

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