Submission #986401

#	Time	Username	Problem	Language	Result	Execution time	Memory
986401		Pyqe	Mechanical Doll (IOI18_doll)	C++17	100 / 100	116 ms	53548 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

long long n,nn,mm,xy[200069][2],am[20][262169];
vector<int> v,vv[2];
bitset<200069> vtd;

void create_circuit(int m,vector<int> a)
{
	long long i,j,ii,p,k,l,c;
	
	a.push_back(0);
	n=a.size();
	for(i=0;i<m+1;i++)
	{
		v.push_back(-1);
	}
	for(nn=1;nn<n;nn*=2);
	mm=nn-1;
	for(k=(nn-n)/2;k>0;mm-=k,k/=2);
	c=mm;
	for(i=0;i<nn;i++)
	{
		if(i<nn-n)
		{
			am[0][i]=1;
		}
		else
		{
			am[0][i]=0;
		}
	}
	for(i=1;1<<i<=nn;i++)
	{
		for(j=0;j<nn;j+=1<<i)
		{
			if(am[i-1][j+(1<<i-1)]==1)
			{
				am[i][j]=1;
			}
			else
			{
				am[i][j]=c;
				for(ii=0;ii<2;ii++)
				{
					xy[c][ii]=-am[i-1][j+ii*(1<<i-1)];
				}
				c--;
			}
		}
	}
	for(i=0;i<n;i++)
	{
		for(p=1;1;)
		{
			k=-xy[p][vtd[p]];
			vtd[p]=!vtd[p];
			if(k==0)
			{
				xy[p][!vtd[p]]=a[i];
				break;
			}
			p=k;
		}
	}
	for(i=1;i<=mm;i++)
	{
		for(ii=0;ii<2;ii++)
		{
			vv[ii].push_back(xy[i][ii]);
		}
	}
	answer(v,vv[0],vv[1]);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:39:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |    if(am[i-1][j+(1<<i-1)]==1)
      |                     ~^~
doll.cpp:48:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   48 |      xy[c][ii]=-am[i-1][j+ii*(1<<i-1)];
      |                                  ~^~
doll.cpp:12:23: warning: unused variable 'l' [-Wunused-variable]
   12 |  long long i,j,ii,p,k,l,c;
      |                       ^

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