제출 #1228747

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

doll

// In the name of Allah

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 4;

int n, m, sz, szx; int A[maxn];
vector<int> Ax, ls;
vector<int> Rx, R1, R2;

void oprx(int l, int r) {
	if (r - l <= 1) return ;
	int mid = (l + r) / 2;
	oprx(l, mid); oprx(mid, r);
	vector<int> A1, A2;
	for (int i = l; i < r; i++) {
		if (i < mid) A1.pb(Ax[i]);
		else A2.pb(Ax[i]);
	}
	for (int i = l; i < r; i++) {
		if ((i - l) % 2 == 0) Ax[i] = A1[(i - l) / 2];
		else Ax[i] = A2[(i - l) / 2];
	}
}

int addx() {
	szx++; R1.pb(-1); R2.pb(-1);
	return -szx;
}

int solvex(vector<int> A) {
	if (*max_element(all(A)) == *min_element(all(A))) {
		return A[0];
	}
	int v = addx();
	vector<int> A1, A2;
	for (int i = 0; i < len(A); i++) {
		if (i % 2 == 0) A1.pb(A[i]);
		else A2.pb(A[i]);
	}
	int u1 = solvex(A1); int u2 = solvex(A2);
	int j = (-v) - 1;
	R1[j] = u1; R2[j] = u2;
	return v;
}

void create_circuit(int M, vector<int> Fx) {
	n = len(Fx); m = M;
	for (int i = 0; i < n; i++) A[i] = Fx[i];
	A[n] = 0; n++;
	sz = (1 << __lg(n));
	if (sz < n) sz *= 2;
	for (int i = 0; i < sz; i++) {
		if (i < sz - n) Ax.pb(0);
		else Ax.pb(1);
	}
	oprx(0, sz);
	int j = 0; ls.resize(sz);
	for (int i = 0; i < sz; i++) {
		if (Ax[i] == 0) ls[i] = -1;
		else {
			ls[i] = A[j]; j++;
		}
	}
	int v = solvex(ls);
	Rx.resize(m + 1); fill(all(Rx), -1);
	answer(Rx, R1, R2);
}

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