제출 #515684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515684		ymm	자동 인형 (IOI18_doll)	C++17	100 / 100	105 ms	10868 KiB

doll

///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

#include "doll.h"

const int N = 1e6+10;
int n, lg, cnt;
int x[N], y[N];
bool sd[N];
vector<int> C;

//void answer(vector<int> C, vector<int> X, vector<int> Y){
//	for(int x : C) cout << x << ' '; cout << '\n';
//	for(int x : X) cout << x << ' '; cout << '\n';
//	for(int x : Y) cout << x << ' '; cout << '\n';
//}

int make(int sz){
	if(sz==1) return 0;
	int i = cnt++;
	x[i] = make(sz/2);
	y[i] = make(sz/2);
	return ~i;
}

int& find(int v=0){
	return (sd[v]=!sd[v])? (x[v]?find(~x[v]):x[v]): (y[v]?find(~y[v]):y[v]);
}

void create_circuit(int m, vector<int> a)
{
	n = a.size();
	C.resize(m+1);
	C[0] = a[0];
	if(n==1){
		answer(C, {}, {});
		return;
	}
	Loop(i,1,m+1) C[i] = -1;
	for(int z=1; z<n; z*=2) ++lg;
	Loop(i,0,lg-1) y[i]=~(i+1);
	cnt = lg;
	for(int i=0,z=1<<(lg-1); z; ++i,z/=2){
		x[i] = (n-1)&z? make(z): -1;
	}
	Loop(i,1,n) find() = a[i];
	auto X = vector<int>(x,x+cnt);
	auto Y = vector<int>(y,y+cnt);
	answer(C,X,Y);
}

//int main(){
//	create_circuit(10, {5});
//}

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