Submission #1221886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221886		boclobanchat	Mechanical Doll (IOI18_doll)	C++20	100 / 100	45 ms	10764 KiB

doll

#include"doll.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+69;
bool ck[MAXN];
int val[MAXN],w[MAXN];
void create_circuit(int M,vector<int> A)
{
	A.push_back(0);
	int n=A.size(),lg=1,cnt=0,c=0;
	while(lg<n) lg*=2,c++;
	for(int i=lg-n+1;i<=lg;i++)
	{
		int pos=i+lg-1;
		while(pos) ck[pos]=true,pos/=2;
	}
	for(int i=1;i<lg*2;i++) if(ck[i]) val[i]=++cnt;
	vector<int> x,y,e;
	for(int i=0;i<=M;i++) e.push_back(-1);
	for(int i=1;i<lg;i++) if(ck[i])
	{
		if(!ck[i*2]) x.push_back(-1);
		else if(i*2<lg) x.push_back(-val[i*2]);
		else x.push_back(0);
		if(!ck[i*2+1]) y.push_back(-1);
		else if(i*2+1<lg) y.push_back(-val[i*2+1]);
		else y.push_back(0);
	}
	int it=0;
	for(int i=0;i<lg;i++) 
	{
		int v=i,res=0;
		for(int j=0;j<c;j++) res=res*2+v%2,v/=2;
		if(ck[res+lg])
		{
			if(res%2==0) x[val[(res+lg)/2]-1]=A[it++];
			else y[val[(res+lg)/2]-1]=A[it++];
		}
	}
	answer(e,x,y);
}

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