oj.uz

Submission #448378

# Submission time Handle Problem Language Result Execution time Memory
448378 2021-07-29T23:43:16 Z JovanB Mechanical Doll (IOI18_doll) C++17
100 / 100
 124 ms 11936 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXC = 1000000;

int L[MAXC];
int R[MAXC];
bool state[MAXC];

int tjm = 1;

vector <int> C;

void init(int node, int n, int d){
    if(d == 1){
        R[node] = MAXC;
        if(n == 1) L[node] = 1;
        else L[node] = MAXC;
        return;
    }
    R[node] = ++tjm;
    int desno = min(n, (1 << (d-1)));
    init(R[node], desno, d-1);
    n -= desno;
    if(n == 0){
        L[node] = 1;
    }
    else{
        L[node]=  ++tjm;
        init(L[node], n, d-1);
    }
}

void descend(int node, int x){
    if(!state[node]){
        state[node] ^= 1;
        if(L[node] == MAXC){
            L[node] = -x;
            return;
        }
        descend(L[node], x);
    }
    else{
        state[node] ^= 1;
        if(R[node] == MAXC){
            R[node] = -x;
            return;
        }
        descend(R[node], x);
    }
}

void create_circuit(int M, std::vector<int> A) {
    A.push_back(0);
    int n = A.size();
    for(int i=0; i<=M; i++) C.push_back(-1);
    int d = 0;
    while((1 << d) < n) d++;
    init(1, n, d);
    for(int i=0; i<n; i++){
        descend(1, A[i]);
    }
    vector <int> _l, _r;
    for(int i=0; i<tjm; i++){
        _l.push_back(-L[i+1]);
        _r.push_back(-R[i+1]);
    }
    answer(C, _l, _r);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 45 ms 4964 KB Output is correct
3 Correct 41 ms 4936 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1604 KB Output is correct
6 Correct 62 ms 6992 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 45 ms 4964 KB Output is correct
3 Correct 41 ms 4936 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1604 KB Output is correct
6 Correct 62 ms 6992 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 79 ms 7852 KB Output is correct
9 Correct 82 ms 8272 KB Output is correct
10 Correct 123 ms 11620 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 45 ms 4964 KB Output is correct
3 Correct 41 ms 4936 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 11 ms 1604 KB Output is correct
6 Correct 62 ms 6992 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 79 ms 7852 KB Output is correct
9 Correct 82 ms 8272 KB Output is correct
10 Correct 123 ms 11620 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 118 ms 11328 KB Output is correct
15 Correct 75 ms 8260 KB Output is correct
16 Correct 124 ms 11936 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 117 ms 11384 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 68 ms 6508 KB Output is correct
3 Correct 69 ms 6392 KB Output is correct
4 Correct 112 ms 9760 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 68 ms 6508 KB Output is correct
3 Correct 69 ms 6392 KB Output is correct
4 Correct 112 ms 9760 KB Output is correct
5 Correct 116 ms 11764 KB Output is correct
6 Correct 112 ms 10300 KB Output is correct
7 Correct 111 ms 10416 KB Output is correct
8 Correct 114 ms 11136 KB Output is correct
9 Correct 74 ms 6520 KB Output is correct
10 Correct 110 ms 10056 KB Output is correct
11 Correct 108 ms 9756 KB Output is correct
12 Correct 72 ms 6508 KB Output is correct
13 Correct 74 ms 7764 KB Output is correct
14 Correct 73 ms 6900 KB Output is correct
15 Correct 89 ms 7020 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 68 ms 7712 KB Output is correct
18 Correct 71 ms 6476 KB Output is correct
19 Correct 70 ms 6420 KB Output is correct
20 Correct 114 ms 10980 KB Output is correct
21 Correct 112 ms 9764 KB Output is correct
22 Correct 107 ms 9708 KB Output is correct