Submission #295056

#	Time	Username	Problem	Language	Result	Execution time	Memory
295056		Saboon	Mechanical Doll (IOI18_doll)	C++17	37 / 100	196 ms	9900 KiB

doll

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

vector<int> X,Y;
vector<int> mark;

int build(int id, int L, int R, int x){
	if (L+1 == R)
		return -x;
	int mid = (L + R) >> 1;
	if (mark[id] == 0)
		X[id-1] = build(2*id+0, L, mid, x);
	else
		Y[id-1] = build(2*id+1, mid, R, x);
	mark[id] ^= 1;
	return id;
}

void create_circuit(int m, vector<int> A){
	int n = A.size();
	int Sz = n+1;
	while (__builtin_popcount(Sz) != 1)
		Sz ++;
	cerr << Sz << endl;
	X.resize(Sz-1), Y.resize(Sz-1), mark.resize(Sz-1);
	vector<int> C(m+1);
	for (int i = 0; i <= m; i++)
		C[i] = -1;
	for (int i = 0; i < n; i++)
		build(1, 0, Sz, A[i]);
	for (int i = n; i < Sz-1; i++)
		build(1, 0, Sz, -1);
	build(1, 0, Sz, 0);
	for (int i = 0; i < Sz-1; i++)
		X[i] *= -1, Y[i] *= -1;
	answer(C, X, Y);

}

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