제출 #1199231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199231		Gr1sen	Mechanical Doll (IOI18_doll)	C++20	79.38 / 100	455 ms	12920 KiB

doll

#include "doll.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<iomanip>
#include<unordered_map>
#include<cmath>
#include<math.h>

using namespace std;

#define vi vector<int>
#define vvi vector<vi>

void print(vi &L) {
	cerr << "{";
	for (auto i : L) cerr << i << ", ";
	cerr << "}" << endl;
}

vi X, Y;

int oi(int a) {
	return -a-1;
}

int oink(int s, int k, int d) {
	//cerr << "oink(" << s << ", " << k << ", " << d << ")" << endl;
	int p = X.size();
	if (k <= 0) return s;
	if (d <= 1) {
		if (k == 1) return 0;
		X.push_back(0);
		Y.push_back(0);
		return oi(p);
	}
	X.push_back(0);
	Y.push_back(0);
	int a = pow(2, (int)log2(k));
	if (a >= k) a /= 2;
	//cerr << "a : " << a << endl;
	Y[p] = oink(s, a, d-1);
	X[p] = oink(s, k-a, d-1);
	return oi(p);
}

void oinkoink(vi &L, vi &K, int p, int pl, int s) {
	/*
	cerr << "oinkoink(..." << p << ", " << pl << ", " << s << ")" << endl;
	print(L);
	print(K);
	print(X);
	print(Y);
	//*/
	if (pl >= L.size()) return;
	if (K[oi(p)]) {
		K[oi(p)] = 0;
		if (Y[oi(p)] == 0) {
			Y[oi(p)] = L[pl];
			oinkoink(L, K, s, pl+1, s);
			return;
		}
		oinkoink(L, K, Y[oi(p)], pl, s);
		return;
	}
	K[oi(p)] = 1;
	if (X[oi(p)] == 0) {
		X[oi(p)] = L[pl];
		oinkoink(L, K, s, pl+1, s);
		return;
	}
	oinkoink(L, K, X[oi(p)], pl, s);
}

void create_circuit(int m, vector<int> A) {
	int n = A.size();
	A.push_back(0);
	vi C(m + 1, 0);
	X.clear(); Y.clear();
	vvi L(m+1);
	L[0] = {A[0]};
	for (int i = 0; i < n; i++) {
		L[A[i]].push_back(A[i+1]);
	}
	int l = 0;
	for (int i = 0; i < m+1; i++) {
		/*
		cerr << "iteration : " << i << endl;
		cerr << "C : ";
		print(C);
		cerr << "X : ";
		print(X);
		cerr << "Y : ";
		print(Y);
		//*/
		if (L[i].size() == 0) continue;
		if (L[i].size() == 1) {
			C[i] = L[i][0];
			continue;
		}
		int a = (int)log2(L[i].size());
		int b = pow(2, a);
		if (b == L[i].size()) {
			b /= 2;
			a--;
		}
		X.push_back(-1);
		Y.push_back(-1);
		int p = X.size()-1;
		C[i] = oi(p);
		X[p] = oink(oi(p), L[i].size()-b, a+1);
		Y[p] = oink(oi(p), b, a+1);
		vi K(X.size(), 0);
		oinkoink(L[i], K, oi(p), 0, oi(p));
	}
	/*
	cerr << "C : ";
	print(C);
	cerr << "X : ";
	print(X);
	cerr << "Y : ";
	print(Y);
	//*/
	answer(C, X, Y);
}

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