Submission #198394

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
198394	2020-01-25T21:11:02 Z	SuperJava	Mechanical Doll (IOI18_doll)	C++17	6 / 100	114 ms	14076 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);
			}
		}
	}
	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	38 ms	8696 KB	Output is correct
3	Correct	40 ms	8288 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	19 ms	6092 KB	Output is correct
6	Correct	67 ms	10052 KB	Output is correct
7	Correct	3 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	38 ms	8696 KB	Output is correct
3	Correct	40 ms	8288 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	19 ms	6092 KB	Output is correct
6	Correct	67 ms	10052 KB	Output is correct
7	Correct	3 ms	4940 KB	Output is correct
8	Correct	54 ms	10304 KB	Output is correct
9	Correct	67 ms	11000 KB	Output is correct
10	Correct	98 ms	13420 KB	Output is correct
11	Correct	5 ms	4940 KB	Output is correct
12	Correct	5 ms	4940 KB	Output is correct
13	Correct	5 ms	4940 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4940 KB	Output is correct
2	Correct	38 ms	8696 KB	Output is correct
3	Correct	40 ms	8288 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	19 ms	6092 KB	Output is correct
6	Correct	67 ms	10052 KB	Output is correct
7	Correct	3 ms	4940 KB	Output is correct
8	Correct	54 ms	10304 KB	Output is correct
9	Correct	67 ms	11000 KB	Output is correct
10	Correct	98 ms	13420 KB	Output is correct
11	Correct	5 ms	4940 KB	Output is correct
12	Correct	5 ms	4940 KB	Output is correct
13	Correct	5 ms	4940 KB	Output is correct
14	Correct	114 ms	14076 KB	Output is correct
15	Incorrect	33 ms	7416 KB	wrong motion
16	Halted	0 ms	0 KB	-