oj.uz

Submission #1077673

# Submission time Handle Problem Language Result Execution time Memory
1077673 2024-08-27T08:33:27 Z s_tree Mechanical Doll (IOI18_doll) C++17
100 / 100
 117 ms 21468 KB 
#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+1);
		y.resize(nodecnt+1);

    answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15960 KB Output is correct
2 Correct 35 ms 17240 KB Output is correct
3 Correct 39 ms 17496 KB Output is correct
4 Correct 5 ms 15964 KB Output is correct
5 Correct 11 ms 16420 KB Output is correct
6 Correct 49 ms 17756 KB Output is correct
7 Correct 5 ms 15960 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15960 KB Output is correct
2 Correct 35 ms 17240 KB Output is correct
3 Correct 39 ms 17496 KB Output is correct
4 Correct 5 ms 15964 KB Output is correct
5 Correct 11 ms 16420 KB Output is correct
6 Correct 49 ms 17756 KB Output is correct
7 Correct 5 ms 15960 KB Output is correct
8 Correct 84 ms 18260 KB Output is correct
9 Correct 59 ms 18644 KB Output is correct
10 Correct 87 ms 21468 KB Output is correct
11 Correct 4 ms 15964 KB Output is correct
12 Correct 6 ms 15964 KB Output is correct
13 Correct 5 ms 15928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15960 KB Output is correct
2 Correct 35 ms 17240 KB Output is correct
3 Correct 39 ms 17496 KB Output is correct
4 Correct 5 ms 15964 KB Output is correct
5 Correct 11 ms 16420 KB Output is correct
6 Correct 49 ms 17756 KB Output is correct
7 Correct 5 ms 15960 KB Output is correct
8 Correct 84 ms 18260 KB Output is correct
9 Correct 59 ms 18644 KB Output is correct
10 Correct 87 ms 21468 KB Output is correct
11 Correct 4 ms 15964 KB Output is correct
12 Correct 6 ms 15964 KB Output is correct
13 Correct 5 ms 15928 KB Output is correct
14 Correct 85 ms 21116 KB Output is correct
15 Correct 61 ms 18008 KB Output is correct
16 Correct 86 ms 20732 KB Output is correct
17 Correct 5 ms 16216 KB Output is correct
18 Correct 4 ms 15964 KB Output is correct
19 Correct 4 ms 15964 KB Output is correct
20 Correct 84 ms 21392 KB Output is correct
21 Correct 5 ms 15964 KB Output is correct
22 Correct 4 ms 15964 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15964 KB Output is correct
2 Correct 53 ms 17888 KB Output is correct
3 Correct 56 ms 18012 KB Output is correct
4 Correct 78 ms 19452 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15964 KB Output is correct
2 Correct 53 ms 17888 KB Output is correct
3 Correct 56 ms 18012 KB Output is correct
4 Correct 78 ms 19452 KB Output is correct
5 Correct 87 ms 20756 KB Output is correct
6 Correct 86 ms 20392 KB Output is correct
7 Correct 86 ms 20480 KB Output is correct
8 Correct 80 ms 20220 KB Output is correct
9 Correct 56 ms 18012 KB Output is correct
10 Correct 84 ms 20096 KB Output is correct
11 Correct 117 ms 19800 KB Output is correct
12 Correct 55 ms 18012 KB Output is correct
13 Correct 51 ms 18008 KB Output is correct
14 Correct 55 ms 18008 KB Output is correct
15 Correct 57 ms 18012 KB Output is correct
16 Correct 6 ms 15964 KB Output is correct
17 Correct 53 ms 18008 KB Output is correct
18 Correct 53 ms 18008 KB Output is correct
19 Correct 59 ms 18012 KB Output is correct
20 Correct 77 ms 19824 KB Output is correct
21 Correct 78 ms 19712 KB Output is correct
22 Correct 75 ms 19708 KB Output is correct