Submission #74905

#	Time	Username	Problem	Language	Result	Execution time	Memory
74905		khsoo01	Mechanical Doll (IOI18_doll)	C++14	100 / 100	140 ms	9348 KiB

doll

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

const int N = 200005, G = 18;

int n, m, g, cc = 1;
bool on[G];

vector<int> c, x, y, a[G];

int rev (int I, int S) {
	int R = 0;
	for(int i=1;i<S;i*=2) {
		if(I & i) R += S/2/i;
	}
	return R;
}

void create_circuit (int M, vector<int> A) {
	n = A.size();
	m = M;
	for(int i=1;i-1<n;i*=2) {
		g++;
	}
	for(int i=0;i<g;i++) {
		if(n & (1<<(g-i-1))) on[i] = true;
	}
	for(int i=1,j=0;i<=(1<<g)-1;i++) {
		int T = i ^ (i-1);
		for(int i=g;i--;) {
			if(T & (1<<i)) {
				T = i;
				break;
			}
		}
		if(!on[T]) continue;
		a[T].push_back(A[j++]);
	}
	for(int i=0;i<=m;i++) {
		c.push_back(-1);
	}
	for(int i=0;i<g;i++) {
		if(i == g-1) {
			if(on[i]) x.push_back(a[i][0]);
			else x.push_back(-1);
			y.push_back(0);
		}
		else if(!on[i]) {
			x.push_back(-1);
			y.push_back(-(cc+1));
			cc += 1;
		}
		else {
			int S = (1<<(g-i-1));
			x.push_back(-(cc+1));
			y.push_back(-(cc+S));
			for(int j=1;j<S;j++) {
				if(j < S/2) {
					x.push_back(-(cc+2*j));
					y.push_back(-(cc+2*j+1));
				}
				else {
					x.push_back(a[i][rev(2*(j-S/2), S)]);
					y.push_back(a[i][rev(2*(j-S/2)+1, S)]);
				}
			}
			cc += S;
		}
	}
	answer(c, x, y);
}

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