Submission #1077616

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1077616	2024-08-27T08:22:51 Z	s_tree	Mechanical Doll (IOI18_doll)	C++17	84 / 100	100 ms	20728 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
vector<int> x(N), y(N), c(N);
vector<int> state(N);
int nodecnt=0, n, pw=1;
int build(int l, int r) {
	if(l >= r)return 0;
	if(r < pw - n) {
		return -1;
	}
	int mid = (l+r)/2;
	int cur = ++nodecnt;
	x[cur-1] = build(l, mid);
	y[cur-1] = build(mid+1, r);
	return -cur;
}
void ins(int i, int val) {
	if(state[-i]) {
		state[-i]^=1;
		if(y[-i-1] == 0) {
			y[-i-1] = val;
		}
		else {
			ins(y[-i-1], val);
		}
	}
	else {
		state[-i]^=1;
		if(x[-i-1] == 0) {
			x[-i-1] = val;
		}
		else {
			ins(x[-i-1], val);
		}
	}
}
void create_circuit(int M, std::vector<int> A) {
	pw = 1;
	n = A.size();
	c=vector<int>(M+1, -1);
	while(pw < n) {
		pw*=2;
	}
	build(0, pw-1);
	for(int i = 1;i<n;i++) {
		ins(-1, A[i]);
	}
	if(n%2 == 1)ins(-1,-1);
	ins(-1,0);
	c[0] = A[0];
	x.resize(nodecnt);
	y.resize(nodecnt);
	answer(c, x, y);
}

Subtask #1

0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	15960 KB	Output is correct
2	Correct	34 ms	17244 KB	Output is correct
3	Correct	35 ms	17240 KB	Output is correct
4	Correct	6 ms	15964 KB	Output is correct
5	Correct	19 ms	16400 KB	Output is correct
6	Correct	47 ms	17756 KB	Output is correct
7	Incorrect	6 ms	15960 KB	wrong serial number
8	Halted	0 ms	0 KB	-

Subtask #2

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	15960 KB	Output is correct
2	Correct	34 ms	17244 KB	Output is correct
3	Correct	35 ms	17240 KB	Output is correct
4	Correct	6 ms	15964 KB	Output is correct
5	Correct	19 ms	16400 KB	Output is correct
6	Correct	47 ms	17756 KB	Output is correct
7	Incorrect	6 ms	15960 KB	wrong serial number
8	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	15960 KB	Output is correct
2	Correct	34 ms	17244 KB	Output is correct
3	Correct	35 ms	17240 KB	Output is correct
4	Correct	6 ms	15964 KB	Output is correct
5	Correct	19 ms	16400 KB	Output is correct
6	Correct	47 ms	17756 KB	Output is correct
7	Incorrect	6 ms	15960 KB	wrong serial number
8	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	15960 KB	Output is correct
2	Correct	6 ms	15964 KB	Output is correct
3	Correct	6 ms	15964 KB	Output is correct
4	Correct	11 ms	15964 KB	Output is correct
5	Correct	7 ms	15960 KB	Output is correct
6	Correct	9 ms	15964 KB	Output is correct
7	Correct	8 ms	15960 KB	Output is correct
8	Correct	7 ms	15964 KB	Output is correct

Subtask #5

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	15964 KB	Output is correct
2	Correct	56 ms	18016 KB	Output is correct
3	Correct	59 ms	18012 KB	Output is correct
4	Correct	80 ms	19200 KB	Output is correct

Subtask #6

56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	15964 KB	Output is correct
2	Correct	56 ms	18016 KB	Output is correct
3	Correct	59 ms	18012 KB	Output is correct
4	Correct	80 ms	19200 KB	Output is correct
5	Correct	88 ms	20728 KB	Output is correct
6	Correct	85 ms	20476 KB	Output is correct
7	Correct	91 ms	20428 KB	Output is correct
8	Correct	100 ms	20216 KB	Output is correct
9	Correct	83 ms	18004 KB	Output is correct
10	Correct	82 ms	20108 KB	Output is correct
11	Correct	82 ms	19704 KB	Output is correct
12	Correct	59 ms	18012 KB	Output is correct
13	Correct	57 ms	18008 KB	Output is correct
14	Correct	55 ms	18012 KB	Output is correct
15	Correct	57 ms	18016 KB	Output is correct
16	Correct	8 ms	15960 KB	Output is correct
17	Correct	56 ms	17884 KB	Output is correct
18	Correct	55 ms	18016 KB	Output is correct
19	Correct	55 ms	18008 KB	Output is correct
20	Correct	85 ms	19960 KB	Output is correct
21	Correct	82 ms	19536 KB	Output is correct
22	Correct	84 ms	19784 KB	Output is correct