제출 #287805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287805		AlanChen	자동 인형 (IOI18_doll)	C++14	100 / 100	186 ms	10292 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,m,bn,s,ful;

int tgt[mx];
int out[2][mx];

bool state[mx];

int makenet(int dpt)
{
	if(dpt==0) return 0;
	int ts=s;
	s++;
	out[0][ts]=makenet(dpt-1);
	out[1][ts]=makenet(dpt-1);
	return -ts;
}

void explore(int v,int p)
{
	if(v==0)
	{
		out[!state[p]][p]=tgt[ful],ful++;
		return;
	}
	state[v]=!state[v];
	explore(-out[!state[v]][v],v);
}

void create_circuit(int M, vi A)
{
	m=M;
	n=sz(A);
	lp(i,n) tgt[i]=A[i];

	vi bita;
	{
		int i1=n;
		while(i1>0) bita.pb(i1%2),i1/=2;
	}
	bn=sz(bita);


	lp(i,1,bn) out[1][i]=-(i+1);
	out[1][bn]=0;

	s=bn+1;
	lp(i,1,bn+1) out[0][i]=bita[bn-i]?makenet(bn-i):-1;

	lp(i,1,s+1) state[i]=0;
	ful=0;
	lp(n) explore(1,-1);


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

	vi X,Y;

	lp(i,1,s) X.pb(out[0][i]);
	lp(i,1,s) Y.pb(out[1][i]);


	answer(C, 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