Submission #198395

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
198395	2020-01-25T21:12:11 Z	SuperJava	Mechanical Doll (IOI18_doll)	C++17	16 / 100	112 ms	14080 KB

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&(digits-k)) > 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&(digits-k)) > 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.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4940 KB	Output is correct
2	Correct	39 ms	8720 KB	Output is correct
3	Correct	33 ms	8324 KB	Output is correct
4	Correct	6 ms	4944 KB	Output is correct
5	Correct	14 ms	6092 KB	Output is correct
6	Correct	39 ms	10052 KB	Output is correct
7	Correct	5 ms	4940 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4940 KB	Output is correct
2	Correct	39 ms	8720 KB	Output is correct
3	Correct	33 ms	8324 KB	Output is correct
4	Correct	6 ms	4944 KB	Output is correct
5	Correct	14 ms	6092 KB	Output is correct
6	Correct	39 ms	10052 KB	Output is correct
7	Correct	5 ms	4940 KB	Output is correct
8	Correct	53 ms	10372 KB	Output is correct
9	Correct	65 ms	10980 KB	Output is correct
10	Correct	88 ms	13392 KB	Output is correct
11	Correct	5 ms	4940 KB	Output is correct
12	Correct	4 ms	4940 KB	Output is correct
13	Correct	5 ms	4940 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4940 KB	Output is correct
2	Correct	39 ms	8720 KB	Output is correct
3	Correct	33 ms	8324 KB	Output is correct
4	Correct	6 ms	4944 KB	Output is correct
5	Correct	14 ms	6092 KB	Output is correct
6	Correct	39 ms	10052 KB	Output is correct
7	Correct	5 ms	4940 KB	Output is correct
8	Correct	53 ms	10372 KB	Output is correct
9	Correct	65 ms	10980 KB	Output is correct
10	Correct	88 ms	13392 KB	Output is correct
11	Correct	5 ms	4940 KB	Output is correct
12	Correct	4 ms	4940 KB	Output is correct
13	Correct	5 ms	4940 KB	Output is correct
14	Correct	112 ms	14080 KB	Output is correct
15	Correct	57 ms	9720 KB	Output is correct
16	Correct	86 ms	12152 KB	Output is correct
17	Correct	4 ms	4940 KB	Output is correct
18	Correct	5 ms	4940 KB	Output is correct
19	Correct	5 ms	4940 KB	Output is correct
20	Correct	109 ms	13456 KB	Output is correct
21	Correct	5 ms	4940 KB	Output is correct
22	Correct	4 ms	4940 KB	Output is correct