제출 #1062228

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

doll

// Author: Kajetan Ramsza
#include "bits/stdc++.h"
#include "doll.h"
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#ifdef DEBUG
auto& operator<<(auto& os, pair<auto, auto> &p);
auto& operator<<(auto &os, const auto &v) 
  { os<<"{"; for(auto it=begin(v);it!=end(v);++it) {
    if(it != begin(v)) { os<<", "; } os<<(*it);
  } return os<<"}"; }
auto& operator<<(auto &os, pair<auto, auto> &p) 
  { return os<<"("<<p.first<<", "<<p.second<<")"; }

void dbg_out(auto... x) { ((cerr<<' '<<x), ...) << endl; }
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x)
#else
#define dbg(...)
#endif

int n, m, s;
vi a;
vi X, Y;
vi state;
int tim = 0;

int create_node(int a, int b) {
	X.push_back(a);
	Y.push_back(b);
	return sz(X);
}

int create_tree(int k, int depth) {
	dbg(k, depth);
	if(depth == 1) {
		if(k == 2) return create_node(-1, -1);
		if(k == 1) return create_node(0, -1);
		assert(false);
	}
	int p = 1<<(depth-1);
	if(k <= p) {
		int index = create_tree(k, depth-1);
		return create_node(0, index);
	}
	int a = create_tree(p, depth-1);
	int b = create_tree(k - p, depth-1);
	return create_node(a, b);
}

void simulate(int v) {
	dbg(v, tim);
	int &x = state[v-1] ? X[v-1] : Y[v-1];
	state[v-1] ^= 1;
	if(x == -1) x = -a[tim++];
	else simulate(x);
}

void create_circuit(int M, vi A) {
	dbg(m);
	a = A;
	a.push_back(0);
	n = a.size();
	m = M;
	int l = (int)ceil(log2(n));
	dbg(l);
	int root = create_tree(n, l);
	dbg(root);
	s = sz(X);
	rep(i,0,s)
		if(X[i] == 0) 
			X[i] = root;
	dbg(s, X, Y);
	state.assign(s, 1);
	rep(i,0,n) {
		dbg(i);
		simulate(root);
	}

	rep(i,0,s) {
		X[i] *= -1;
		Y[i] *= -1;
	}

	vi C(M + 1, -root);
	dbg(X, Y);
	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