oj.uz

Submission #823600

# Submission time Handle Problem Language Result Execution time Memory
823600 2023-08-12T20:17:29 Z someone Mechanical Doll (IOI18_doll) C++14
100 / 100
 108 ms 11700 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 42;

int id = 0, n;
vector<int> nxt[2], state;

int tree(int lvl, int deb) {
    if(deb >= n) return -INF;
    if(lvl == 0) return 0;
    lvl--;
    int mid = deb + (1 << (lvl));
    int right = tree(lvl, deb), left = tree(lvl, mid);
    nxt[0].push_back(left);
    nxt[1].push_back(right);
    return --id;
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    n = (int)A.size();
    vector<int> C(M + 1);
    if(n == 2) {
        C[0] = 1, C[1] = 0;
        answer(C, nxt[0], nxt[1]);
        return;
    }
    int len = 0;
    while((1 << len) <= n) len++;
    tree(len, 0);
    int sz = (int)nxt[0].size();
    for (int i = 0; i <= M; ++i)
        C[i] = -sz;
    for(int i = 0; i < sz; i++) {
        if(nxt[0][i] == -INF)
            nxt[0][i] = -sz;
        if(nxt[1][i] == -INF)
            nxt[1][i] = -sz;
    }
    state.resize((int)nxt[0].size());
    id = 0;
    int i = sz-1;
    while(i != -1) {
        int nex = -nxt[state[i]][i]-1;
        if(nxt[state[i]][i] == 0) {
            nxt[state[i]][i] = A[id++];
            nex = sz-1;
            if(nxt[state[i]][i] == 0) nex = -1;
        }
        state[i] = 1 - state[i];
        i = nex;
    }
    answer(C, nxt[0], nxt[1]);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 36 ms 4496 KB Output is correct
3 Correct 33 ms 4636 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 52 ms 6764 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 36 ms 4496 KB Output is correct
3 Correct 33 ms 4636 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 52 ms 6764 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 71 ms 7844 KB Output is correct
9 Correct 70 ms 8552 KB Output is correct
10 Correct 102 ms 11700 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 36 ms 4496 KB Output is correct
3 Correct 33 ms 4636 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 52 ms 6764 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 71 ms 7844 KB Output is correct
9 Correct 70 ms 8552 KB Output is correct
10 Correct 102 ms 11700 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 304 KB Output is correct
14 Correct 108 ms 10932 KB Output is correct
15 Correct 66 ms 7228 KB Output is correct
16 Correct 97 ms 10620 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 103 ms 11312 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 63 ms 5560 KB Output is correct
3 Correct 65 ms 5564 KB Output is correct
4 Correct 94 ms 8348 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 63 ms 5560 KB Output is correct
3 Correct 65 ms 5564 KB Output is correct
4 Correct 94 ms 8348 KB Output is correct
5 Correct 99 ms 9892 KB Output is correct
6 Correct 97 ms 9480 KB Output is correct
7 Correct 97 ms 9708 KB Output is correct
8 Correct 95 ms 9192 KB Output is correct
9 Correct 62 ms 5576 KB Output is correct
10 Correct 97 ms 9172 KB Output is correct
11 Correct 99 ms 8760 KB Output is correct
12 Correct 62 ms 5852 KB Output is correct
13 Correct 62 ms 6260 KB Output is correct
14 Correct 66 ms 6360 KB Output is correct
15 Correct 65 ms 6560 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 65 ms 6184 KB Output is correct
18 Correct 62 ms 5740 KB Output is correct
19 Correct 61 ms 5812 KB Output is correct
20 Correct 94 ms 8984 KB Output is correct
21 Correct 97 ms 8720 KB Output is correct
22 Correct 94 ms 8868 KB Output is correct