Submission #286685

#	Time	Username	Problem	Language	Result	Execution time	Memory
286685		AlanChen	Mechanical Doll (IOI18_doll)	C++14	9 / 100	237 ms	12320 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>
using namespace std;

template<class A> using v=vector<A>;

typedef v<int> vi;

#define sz(S) (int)(S).size()
#define pb push_back



#define get4(a,b,c,d,...) d

#define lp3(x,a,b) for(int x=(a);x<(b);x++)
#define lp2(x,a) lp3(x,0,a)
#define lp1(a) lp2(loopvar,a)
#define lp(x...) get4(x,lp3,lp2,lp1,0)(x)


#define trv(x,S) for(auto& x:(S))


const int mx=800100;
int n;

int tgt[mx];

int cnnct[mx];
int outx[mx];
int outy[mx];
bool stt[mx];


void create_circuit(int m, vi A)
{
	vi C(m+1);
	vi X,Y;
	if(sz(A)==1)
	{
		lp(i,m+1) C[i]=0;
		C[0]=A[0];
		C[A[0]]=0;
		answer(C,X,Y);
		return;
	}


	A.pb(0);
	n=2; while(n<=sz(A)) n*=2;
	lp(i,n-sz(A)) tgt[i]=-1;
	lp(i,sz(A)) tgt[n-sz(A)+i]=A[i];

	lp(i,1,n/2) outx[i]=2*i,outy[i]=2*i+1;
	trv(x,stt) x=true;
	lp(tmp,0,n)
	{
		int x=1;
		while(x<n/2) stt[x]=!stt[x],x=2*x+stt[x];
		stt[x]=!stt[x];
		if(stt[x]) outy[x]=tgt[tmp];
		else outx[x]=tgt[tmp];
	}
	lp(i,1,n/2) outx[i]*=-1,outy[i]*=-1;


	lp(i,m+1) C[i]=-1;


	lp(i,1,n) X.pb(outx[i]);
	lp(i,1,n) Y.pb(outy[i]);


	answer(C, X, Y);
}

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