Submission #312584

#	Time	Username	Problem	Language	Result	Execution time	Memory
312584		tengiz05	Mechanical Doll (IOI18_doll)	C++17	0 / 100	2 ms	204 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;
int sz=1, n, cnt=0;/*
int state[700005];
int get(int node){
	if(node >= sz){
		return (sz-n <= node-sz)?node-sz:inf;
	}
	state[node] = (state[node]+1)%2;
	if(state[node])return get(node*2);
	else return get(node*2+1);
}*/
void create_circuit(int m, vector<int> a) {
	a.push_back(0);
	n = a.size();
	while(sz < n)sz<<=1;
	vector<int> t(sz*2);
	for(int i=0;i<sz;i++)t[i+sz] = inf;
	int tt = 0;
	vector<int> rev;
	vector<int> used(sz*2);
	rev.push_back(0);
	for(int div = sz/2; div > 1; div >>= 1){
		int d = div;
		while(d < sz){
			if(!used[d])rev.push_back((sz-n <= d)?d:inf);
			used[d] = 1;
			d += div;
		}
	}for(int i=0;i<sz/2;i++)rev.push_back(rev[i]+1 >= sz-n && rev[i] != inf? rev[i]+1: inf);
//	for(auto x : rev)cout << x << ' ';
	int j = 0;
	for(int i=0;i<sz;i++){
		if(rev[i] != inf)t[rev[i]+sz] = a[j], j++;
	}
	vector<int> X, Y;
	for(int i=sz-1; i>0; i--){
		if(t[i*2] == inf && t[i*2+1] == inf)t[i] = inf;
		else {
			t[i] = --tt;
			X.push_back(t[i*2]);
			Y.push_back(t[i*2+1]);
		}
	}for(int i=0;i<(int)X.size();i++){
		if(X[i] == inf)X[i] = tt;
		if(Y[i] == inf)Y[i] = tt;
	}
	answer(vector<int>(m+1, tt), X, Y);
}

/*

1 1
1

*/

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