Submission #198396

#	Time	Username	Problem	Language	Result	Execution time	Memory
198396		SuperJava	Mechanical Doll (IOI18_doll)	C++17	53 / 100	143 ms	17832 KiB

doll

#include "doll.h"
#include <vector>
#include <utility>
#include <iostream>
#define sz(A) int(size(A))
using namespace std;

vector<int> adj[200005];
vector<int> v = {2,4,8,16,32,64,128,256,512,1024,2048,
				4096,8192,16384,32768,65536,131072,
				262144};

int dig(int x){
	int ans = 0;
	while(x != 1){
		x /= 2;
		ans++;
	}
	return ans;
}

void create_circuit(int M, vector<int> A) {
	for(int i = 0; i < sz(A)-1; i++){
		adj[A[i]].push_back(A[i+1]);
	}
	adj[A[sz(A)-1]].push_back(0);
	vector<int> C(M+1);
	C[0] = A[0];
	vector<int> X,Y;
	for(int i = 1; i <= M; i++){
		int w = sz(adj[i]);
		if(w == 0) continue;
		if(w == 1){
			C[i] = adj[i][0];
			continue;
		}
		if(w == 2){
			C[i] = -(sz(X)+1);
			X.push_back(adj[i][0]);
			Y.push_back(adj[i][1]);
			continue;
		}
		if((w&(w-1))){
			C[i] = -(sz(X)+1);
			int fulen = *lower_bound(v.begin(), v.end(),w);
			vector<pair<int,int>> news(fulen-1);
			for(int j = 0; j < fulen/2-1; j++){
				news[j].first = -(j+1)*2-sz(X);
				news[j].second = -(j+1)*2-sz(X)-1;
			}
			int digits = dig(fulen);
			vector<int> toadd(fulen);
			for(int j = 0; j < w-1; j++){
				toadd[j] = adj[i][j];
			}
			for(int j = w-1; j < fulen-1; j++){
				toadd[j] = -(sz(X)+1);
			}
			toadd[fulen-1] = adj[i][w-1];
			for(int j = 0; j < fulen; j++){
				int res = 0;
				for(int k = 0; k < digits; k++){
					res += (1<<k)*((j&(1<<(digits-k-1))) > 0);
				}
				if(res&1){
					news[res/2+fulen/2-1].second = toadd[j];
				}else{
					news[res/2+fulen/2-1].first = toadd[j];
				}
			}
			for(int j = 0; j < fulen-1; j++){
				X.push_back(news[j].first);
				Y.push_back(news[j].second);
			}
		}else{
			C[i] = -(sz(X)+1);
			int fulen = *lower_bound(v.begin(), v.end(),w);
			vector<pair<int,int>> news(fulen-1);
			for(int j = 0; j < fulen/2-1; j++){
				news[j].first = -(j+1)*2-sz(X);
				news[j].second = -(j+1)*2-sz(X)-1;
			}
			int digits = dig(fulen);
			vector<int> toadd(fulen);
			for(int j = 0; j < w; j++){
				toadd[j] = adj[i][j];
			}
			for(int j = 0; j < fulen; j++){
				int res = 0;
				for(int k = 0; k < digits; k++){
					res += (1<<k)*((j&(1<<(digits-k-1))) > 0);
				}
				if(res&1){
					news[res/2+fulen/2-1].second = toadd[j];
				}else{
					news[res/2+fulen/2-1].first = toadd[j];
				}
			}
			for(int j = 0; j < fulen-1; j++){
				X.push_back(news[j].first);
				Y.push_back(news[j].second);
			}
		}
	}
	answer(C,X,Y);
}

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