Submission #422832

#	Time	Username	Problem	Language	Result	Execution time	Memory
422832		amoo_safar	Mechanical Doll (IOI18_doll)	C++17	28 / 100	166 ms	11864 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second

using namespace std;

vector<int> X, Y;
int uni = 12345678;

int Solve(vector<int> A){
	// cerr << "!! " ;
	// for(auto x : A) cerr << x << ' ';
	// cerr << '\n';

	if(A[0] == -1){
		// X.pb(uni);
		// Y.pb(uni);
		// return -((int) X.size());
		return uni;
	}
	if(A.size() == 1)
		return A[0];
	int n = A.size();
	vector<int> G, B, L, R;
	for(auto x : A)
		(x == -1 ? B : G).pb(x);
	int cnt = 0;
	for(auto x : A)
		cnt += (x >= 0);
	if(cnt <= n / 2){
		for(int i = 0; i < n / 2; i++) L.pb(A[i]);
		for(int i = n / 2; i < n; i++) R.pb(A[i]);
	} else {
		int rm = n - cnt;
		for(int i = 0; i < (n / 2) - rm; i++){
			L.pb(A[i + i]);
			R.pb(A[i + i + 1]);
		}
		int la = ((n / 2) - rm) * 2;
		for(int i = 0; i < rm; i++){
			L.pb(A[la + i]);
			R.pb(-1);
		}
	}
	int lf = Solve(L);
	int rt = Solve(R);
	X.pb(lf);
	Y.pb(rt);
	return -((int) X.size());
}

void create_circuit(int m, vector<int> A) {
	A.pb(0);
	reverse(A.begin(), A.end());
	int n = A.size();
	int sz = n;
	for(int i = 0; i < 30; i++){
		if((1 << i) >= n){
			sz = (1 << i);
			break;
		}
	}
	A.resize(sz, -1);
	// vector<int> B(A.size() - sz);

	int rt = Solve(A);
	vector<int> C(m + 1, rt);

	for(auto &x : X) if(x == uni) x = rt;
	for(auto &x : Y) if(x == uni) x = rt;
	// cerr << "! ";
	// for(auto x : C) cerr << x << ' ';
	// cerr << '\n';
	// cerr << "# ";
	// for(int i = 0; i < X.size(); i++)
	// 	cerr << X[i] << ':' << Y[i] << '\n';
	// cerr << '\n'; 
	answer(C, Y, X);
}

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