제출 #295075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295075		amoo_safar	자동 인형 (IOI18_doll)	C++17	60.67 / 100	168 ms	11312 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

const int N = 4e5 + 100;

int p2[N];

int X[N], Y[N], st[N];

int la = 0;
int Solve(int cnt, int fuck){
	int id = -- la;
	assert((cnt + fuck)%2 == 0);
	//cerr << "# " << id << ' ' << cnt << ' ' << fuck << '\n';
	if(cnt == 0){
		X[-id] = -1;
		Y[-id] = -1;
	} else if(cnt == 1 && fuck == 1){
		X[-id] = -1;
		Y[-id] = N;
	} else if(cnt == 2 && fuck == 0){
		X[-id] = N;
		Y[-id] = N;
	} else {
		int sz = (cnt + fuck)/2;
		int fk = min(fuck, sz);

		X[-id] = Solve(sz - fk, fk);
		Y[-id] = Solve(sz - (fuck - fk), fuck - fk);
	}
	return id;
}

void create_circuit(int M, vector<int> A) {
	for(int i = 0; (1 << i) + 1 < N; i++) p2[(1 << i) + 1] = (1 << i);
	for(int i = 2; i < N; i++) p2[i] = max(p2[i], p2[i - 1]);
	A.pb(0);
	int n = A.size();
	int rt;
	for(int i = 0; ; i++){
		if((1 << i) >= n){
			rt = Solve(n, (1 << i) - n);
			break;
		}
	}
	assert(rt == -1);
	//for(int i = 1; i <= 7; i++) //cerr << "^ " << X[i] << ' ' << Y[i] << '\n';
	int id, nx;
	for(int rq : A){
		id = -1;
		//cerr << "&& " << rq << '\n';
		while(true){
			//if(id >= 0) assert(0);
			nx = st[-id] ? Y[-id] : X[-id];

			//cerr << "nx : " << nx << '\n';
			if(nx == N){
				if(st[-id]) Y[-id] = rq;
				else X[-id] = rq;
				st[-id] ^= 1;
				break;
			}
			//assert(nx < 0);
			st[-id] ^= 1;
			id = nx;
		}
	}
	for(int i = 0; i < N; i++){
		assert(st[i] == 0);
	}
	assert(abs(la) <= n + n);

	vector<int> C(M + 1, -1), aX, aY;
	for(int i = -1; i >= la; i --){
		aX.pb(X[-i]);
		aY.pb(Y[-i]);
	}
	answer(C, aX, aY);
}

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