Submission #198393

# Submission time Handle Problem Language Result Execution time Memory
198393 2020-01-25T21:00:45 Z SuperJava Mechanical Doll (IOI18_doll) C++17
6 / 100
164 ms 14088 KB
#include "doll.h"
#include <vector>
#include <utility>
#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+2)*2-sz(X);
			}
			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].second = toadd[j];
				}else{
					news[res/2].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);
}
# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 40 ms 8660 KB Output is correct
3 Correct 28 ms 8316 KB Output is correct
4 Correct 4 ms 4852 KB Output is correct
5 Correct 14 ms 6092 KB Output is correct
6 Correct 42 ms 10052 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 40 ms 8660 KB Output is correct
3 Correct 28 ms 8316 KB Output is correct
4 Correct 4 ms 4852 KB Output is correct
5 Correct 14 ms 6092 KB Output is correct
6 Correct 42 ms 10052 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 62 ms 10348 KB Output is correct
9 Correct 60 ms 10944 KB Output is correct
10 Correct 86 ms 13360 KB Output is correct
11 Correct 6 ms 4940 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 40 ms 8660 KB Output is correct
3 Correct 28 ms 8316 KB Output is correct
4 Correct 4 ms 4852 KB Output is correct
5 Correct 14 ms 6092 KB Output is correct
6 Correct 42 ms 10052 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 62 ms 10348 KB Output is correct
9 Correct 60 ms 10944 KB Output is correct
10 Correct 86 ms 13360 KB Output is correct
11 Correct 6 ms 4940 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Incorrect 164 ms 14088 KB wrong motion
15 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB wrong motion
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4940 KB wrong serial number
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4940 KB wrong serial number
2 Halted 0 ms 0 KB -