oj.uz

Submission #602878

# Submission time Handle Problem Language Result Execution time Memory
602878 2022-07-23T12:10:27 Z SlavicG Mechanical Doll (IOI18_doll) C++17
100 / 100
 125 ms 49376 KB 
#include "doll.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 5e6;
vector<int> x(N), y(N);
int idx = 0, n, cc[N];
int NN;
int build(int l, int r) {
    if(NN - 1 - r >= n) return -1;
    if(l == r) return 1;
    int mid = l + r >> 1;
    int i = idx++;
    x[i] = build(l, mid);
    y[i] = build(mid + 1, r);
    return -i - 1;
}

void create_circuit(int m, vector<int> a) {
    a.push_back(0);
    n = a.size();
    vector<int> c(m + 1, -1);
    NN = n; while(__builtin_popcount(NN) != 1) ++NN;
    build(0, NN - 1);
    x.resize(idx);
    y.resize(idx);

    for(int i: a) {
        int node = 0;
        while(true) {
            int nxt = (cc[node] ? y[node] : x[node]);
            if(nxt == 1) {
                if(cc[node] == 1) y[node] = i;
                else x[node] = i;
                cc[node] ^= 1;
                break;
            }
            cc[node] ^= 1;
            node = -nxt - 1;
        }
    }
    answer(c, x, y);
}

Compilation message

doll.cpp: In function 'int build(int, int)':
doll.cpp:11:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39380 KB Output is correct
2 Correct 52 ms 42820 KB Output is correct
3 Correct 50 ms 42956 KB Output is correct
4 Correct 15 ms 39460 KB Output is correct
5 Correct 24 ms 40612 KB Output is correct
6 Correct 75 ms 44856 KB Output is correct
7 Correct 15 ms 39380 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39380 KB Output is correct
2 Correct 52 ms 42820 KB Output is correct
3 Correct 50 ms 42956 KB Output is correct
4 Correct 15 ms 39460 KB Output is correct
5 Correct 24 ms 40612 KB Output is correct
6 Correct 75 ms 44856 KB Output is correct
7 Correct 15 ms 39380 KB Output is correct
8 Correct 81 ms 45600 KB Output is correct
9 Correct 83 ms 45932 KB Output is correct
10 Correct 119 ms 48568 KB Output is correct
11 Correct 15 ms 39380 KB Output is correct
12 Correct 15 ms 39456 KB Output is correct
13 Correct 15 ms 39408 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39380 KB Output is correct
2 Correct 52 ms 42820 KB Output is correct
3 Correct 50 ms 42956 KB Output is correct
4 Correct 15 ms 39460 KB Output is correct
5 Correct 24 ms 40612 KB Output is correct
6 Correct 75 ms 44856 KB Output is correct
7 Correct 15 ms 39380 KB Output is correct
8 Correct 81 ms 45600 KB Output is correct
9 Correct 83 ms 45932 KB Output is correct
10 Correct 119 ms 48568 KB Output is correct
11 Correct 15 ms 39380 KB Output is correct
12 Correct 15 ms 39456 KB Output is correct
13 Correct 15 ms 39408 KB Output is correct
14 Correct 121 ms 48120 KB Output is correct
15 Correct 91 ms 45568 KB Output is correct
16 Correct 115 ms 48924 KB Output is correct
17 Correct 20 ms 39380 KB Output is correct
18 Correct 18 ms 39448 KB Output is correct
19 Correct 17 ms 39412 KB Output is correct
20 Correct 114 ms 49376 KB Output is correct
21 Correct 15 ms 39380 KB Output is correct
22 Correct 18 ms 39436 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39444 KB Output is correct
2 Correct 15 ms 39456 KB Output is correct
3 Correct 16 ms 39460 KB Output is correct
4 Correct 15 ms 39440 KB Output is correct
5 Correct 15 ms 39456 KB Output is correct
6 Correct 15 ms 39424 KB Output is correct
7 Correct 14 ms 39380 KB Output is correct
8 Correct 15 ms 39380 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39380 KB Output is correct
2 Correct 76 ms 44600 KB Output is correct
3 Correct 78 ms 44612 KB Output is correct
4 Correct 112 ms 47384 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 39380 KB Output is correct
2 Correct 76 ms 44600 KB Output is correct
3 Correct 78 ms 44612 KB Output is correct
4 Correct 112 ms 47384 KB Output is correct
5 Correct 110 ms 48868 KB Output is correct
6 Correct 125 ms 48484 KB Output is correct
7 Correct 110 ms 48728 KB Output is correct
8 Correct 113 ms 48240 KB Output is correct
9 Correct 73 ms 44564 KB Output is correct
10 Correct 113 ms 48124 KB Output is correct
11 Correct 113 ms 47880 KB Output is correct
12 Correct 76 ms 44808 KB Output is correct
13 Correct 85 ms 45180 KB Output is correct
14 Correct 84 ms 45316 KB Output is correct
15 Correct 82 ms 45460 KB Output is correct
16 Correct 17 ms 39636 KB Output is correct
17 Correct 73 ms 44992 KB Output is correct
18 Correct 75 ms 44852 KB Output is correct
19 Correct 93 ms 44860 KB Output is correct
20 Correct 110 ms 47988 KB Output is correct
21 Correct 111 ms 47716 KB Output is correct
22 Correct 108 ms 47864 KB Output is correct