Submission #132777

#	Time	Username	Problem	Language	Result	Execution time	Memory
132777		TadijaSebez	Mechanical Doll (IOI18_doll)	C++11	100 / 100	197 ms	15516 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
const int M=2*N;
int ls[M],rs[M],root,tsz;
vector<int> Build(vector<int> v)
{
	if(v.size()==1) return v;
	vector<int> u[2];
	for(int i=0;i<v.size();i++) u[i&1].pb(v[i]);
	u[0]=Build(u[0]);
	u[1]=Build(u[1]);
	v.clear();
	for(int i:u[0]) v.pb(i);
	for(int i:u[1]) v.pb(i);
	return v;
}
int n,m,k;
int a[M],pos[M];
bool use[M];
void Build(int &c, int ss, int se)
{
	if(se<=k){ c=root;return;}
	if(ss==se){ c=-a[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);
	m=M;n=A.size();
	int sz=1;
	while(sz<A.size()) sz<<=1;
	vector<int> v;
	for(int i=1;i<=sz;i++) v.pb(i);
	v=Build(v);
	k=sz-n;
	for(int i=k;i<sz;i++)
	{
		use[v[i]]=1;
		pos[v[i]]=i+1;
	}
	for(int i=1,j=0;i<=sz;i++)
	{
		if(use[i])
		{
			a[pos[i]]=A[j];
			j++;
		}
	}
	Build(root,1,sz);
	vector<int> C,X,Y;
	C.assign(m+1,-1);
	for(int i=1;i<=tsz;i++) X.pb(-ls[i]),Y.pb(-rs[i]);
	answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'std::vector<int> Build(std::vector<int>)':
doll.cpp:12:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i=0;i<v.size();i++) u[i&1].pb(v[i]);
      |              ~^~~~~~~~~
doll.cpp: In function 'void Build(int&, int, int)':
doll.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |  int mid=ss+se>>1;
      |          ~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:37:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  while(sz<A.size()) sz<<=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