Submission #1077658

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1077658	2024-08-27T08:31:10 Z	s_tree	Mechanical Doll (IOI18_doll)	C++17	84 / 100	97 ms	19104 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	5 ms	15964 KB	Output is correct
2	Correct	32 ms	16988 KB	Output is correct
3	Correct	32 ms	16732 KB	Output is correct
4	Correct	5 ms	15964 KB	Output is correct
5	Correct	15 ms	16476 KB	Output is correct
6	Correct	51 ms	17256 KB	Output is correct
7	Incorrect	4 ms	15964 KB	wrong serial number
8	Halted	0 ms	0 KB	-

Subtask #2

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	15964 KB	Output is correct
2	Correct	32 ms	16988 KB	Output is correct
3	Correct	32 ms	16732 KB	Output is correct
4	Correct	5 ms	15964 KB	Output is correct
5	Correct	15 ms	16476 KB	Output is correct
6	Correct	51 ms	17256 KB	Output is correct
7	Incorrect	4 ms	15964 KB	wrong serial number
8	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	15964 KB	Output is correct
2	Correct	32 ms	16988 KB	Output is correct
3	Correct	32 ms	16732 KB	Output is correct
4	Correct	5 ms	15964 KB	Output is correct
5	Correct	15 ms	16476 KB	Output is correct
6	Correct	51 ms	17256 KB	Output is correct
7	Incorrect	4 ms	15964 KB	wrong serial number
8	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	15964 KB	Output is correct
2	Correct	4 ms	16092 KB	Output is correct
3	Correct	5 ms	15964 KB	Output is correct
4	Correct	7 ms	15876 KB	Output is correct
5	Correct	4 ms	15964 KB	Output is correct
6	Correct	5 ms	15964 KB	Output is correct
7	Correct	5 ms	15964 KB	Output is correct
8	Correct	4 ms	16064 KB	Output is correct

Subtask #5

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	15964 KB	Output is correct
2	Correct	59 ms	16988 KB	Output is correct
3	Correct	55 ms	17136 KB	Output is correct
4	Correct	85 ms	17824 KB	Output is correct

Subtask #6

56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	15964 KB	Output is correct
2	Correct	59 ms	16988 KB	Output is correct
3	Correct	55 ms	17136 KB	Output is correct
4	Correct	85 ms	17824 KB	Output is correct
5	Correct	92 ms	19104 KB	Output is correct
6	Correct	94 ms	18964 KB	Output is correct
7	Correct	92 ms	18960 KB	Output is correct
8	Correct	87 ms	18588 KB	Output is correct
9	Correct	61 ms	16868 KB	Output is correct
10	Correct	92 ms	18616 KB	Output is correct
11	Correct	92 ms	18128 KB	Output is correct
12	Correct	58 ms	17140 KB	Output is correct
13	Correct	58 ms	16988 KB	Output is correct
14	Correct	64 ms	17112 KB	Output is correct
15	Correct	60 ms	17244 KB	Output is correct
16	Correct	6 ms	15964 KB	Output is correct
17	Correct	63 ms	17132 KB	Output is correct
18	Correct	61 ms	17136 KB	Output is correct
19	Correct	57 ms	17132 KB	Output is correct
20	Correct	87 ms	18352 KB	Output is correct
21	Correct	82 ms	18096 KB	Output is correct
22	Correct	97 ms	18288 KB	Output is correct