oj.uz

Submission #1014956

# Submission time Handle Problem Language Result Execution time Memory
1014956 2024-07-05T19:21:58 Z ThegeekKnight16 Mechanical Doll (IOI18_doll) C++17
100 / 100
 97 ms 10068 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

int build(int qnt, int &extra, vector<int> &X, vector<int> &Y)
{
    if (qnt == 1) return 0;
    if (qnt <= extra)
    {
        extra -= qnt;
        return -1;
    }
    X.push_back(-1); Y.push_back(-1);
    int id = X.size();

    int e = build(qnt/2, extra, X, Y), d = build(qnt/2, extra, X, Y);
    X[id-1] = e, Y[id-1] = d;
    return -id;
}

void create_circuit(int M, std::vector<int> A)
{
    int N = A.size();
    if (N == 1)
    {
        vector<int> C = {A[0], 0};
        vector<int> X, Y;
        answer(C, X, Y);
        return;
    }
    vector<int> X, Y;
    int qnt = 1;
    while (qnt < N) qnt *= 2;
    int extra = qnt - N;
    bool delay = 0;
    if (extra % 2) extra--, delay = 1;
    build(qnt, extra, X, Y);

    vector<int> C(M+1, -1); C[0] = (delay ? -1 : A[0]);
    vector<int> state(X.size());
    for (int i = 1-(int)delay; i < N; i++)
    {
        int id = -1;
        while (id < 0)
        {
            int nextId = (state[-id-1] ? Y[-id-1] : X[-id-1]);
            state[-id-1] ^= 1;
            if (nextId == 0)
            {
                if (state[-id-1]) X[-id-1] = A[i];
                else Y[-id-1] = A[i];
                break;
            }
            id = nextId;
        }
    }
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 26 ms 4568 KB Output is correct
3 Correct 24 ms 4024 KB Output is correct
4 Correct 0 ms 432 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 46 ms 5832 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 26 ms 4568 KB Output is correct
3 Correct 24 ms 4024 KB Output is correct
4 Correct 0 ms 432 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 46 ms 5832 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 61 ms 6748 KB Output is correct
9 Correct 47 ms 7552 KB Output is correct
10 Correct 69 ms 10068 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 26 ms 4568 KB Output is correct
3 Correct 24 ms 4024 KB Output is correct
4 Correct 0 ms 432 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 46 ms 5832 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 61 ms 6748 KB Output is correct
9 Correct 47 ms 7552 KB Output is correct
10 Correct 69 ms 10068 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 97 ms 9664 KB Output is correct
15 Correct 44 ms 6564 KB Output is correct
16 Correct 67 ms 9408 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 68 ms 9732 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 38 ms 5296 KB Output is correct
3 Correct 49 ms 5052 KB Output is correct
4 Correct 67 ms 7612 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 38 ms 5296 KB Output is correct
3 Correct 49 ms 5052 KB Output is correct
4 Correct 67 ms 7612 KB Output is correct
5 Correct 66 ms 7876 KB Output is correct
6 Correct 76 ms 7648 KB Output is correct
7 Correct 65 ms 7656 KB Output is correct
8 Correct 62 ms 7612 KB Output is correct
9 Correct 43 ms 5056 KB Output is correct
10 Correct 65 ms 7612 KB Output is correct
11 Correct 63 ms 7616 KB Output is correct
12 Correct 39 ms 5060 KB Output is correct
13 Correct 50 ms 5068 KB Output is correct
14 Correct 43 ms 5296 KB Output is correct
15 Correct 43 ms 5552 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 40 ms 5088 KB Output is correct
18 Correct 38 ms 5064 KB Output is correct
19 Correct 40 ms 5052 KB Output is correct
20 Correct 66 ms 7640 KB Output is correct
21 Correct 75 ms 7616 KB Output is correct
22 Correct 71 ms 7656 KB Output is correct