oj.uz

Submission #847228

# Submission time Handle Problem Language Result Execution time Memory
847228 2023-09-09T09:56:39 Z 12345678 Mechanical Doll (IOI18_doll) C++17
100 / 100
 91 ms 12472 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+1000;
int cnt, mx, used, id, t;
vector<int> v, X(nx), Y(nx), nv;

void add(int idx, int layer)
{
    used=max(used, idx);
    if (layer==mx)
    {
        if (cnt>=1) Y[idx-1]=v[cnt--], X[idx-1]=v[cnt--];
        else if (cnt==0) Y[idx-1]=v[cnt--], X[idx-1]=-1;
    }
    else
    {
        int sid=id+1;
        add(++id, layer+1);
        Y[idx-1]=-sid;
        sid=id+1;
        if (cnt>=0) add(++id, layer+1), X[idx-1]=-sid;
        else X[idx-1]=-1;
    }
}

void create_circuit(int M, std::vector<int> A) {
    vector<int> C(M+1);
    for (int i=0; i<=M; i++) C[i]=-1;
    v=A;
    v.push_back(0);
    int N=v.size();
    cnt=N-1; mx=ceil(log2(N));
    nv.resize(N);
    reverse(v.begin(), v.end());
    for (int i=0; i<(1<<mx); i++)
    {
        int vl=0;
        for (int j=mx-1; j>=0; j--)
        {
            if ((i/(1<<j))%2!=0) vl+=(1<<(mx-j-1));
        }
        if (vl<N) nv[vl]=v[t++];
    }
    v=nv;
    reverse(v.begin(), v.end());
    add(++id, 1);
    X.resize(used); Y.resize(used);
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 37 ms 5688 KB Output is correct
3 Correct 35 ms 5588 KB Output is correct
4 Correct 1 ms 1880 KB Output is correct
5 Correct 10 ms 3164 KB Output is correct
6 Correct 45 ms 7608 KB Output is correct
7 Correct 1 ms 1880 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 37 ms 5688 KB Output is correct
3 Correct 35 ms 5588 KB Output is correct
4 Correct 1 ms 1880 KB Output is correct
5 Correct 10 ms 3164 KB Output is correct
6 Correct 45 ms 7608 KB Output is correct
7 Correct 1 ms 1880 KB Output is correct
8 Correct 66 ms 8772 KB Output is correct
9 Correct 67 ms 9268 KB Output is correct
10 Correct 84 ms 12472 KB Output is correct
11 Correct 1 ms 1884 KB Output is correct
12 Correct 1 ms 1884 KB Output is correct
13 Correct 1 ms 1880 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 37 ms 5688 KB Output is correct
3 Correct 35 ms 5588 KB Output is correct
4 Correct 1 ms 1880 KB Output is correct
5 Correct 10 ms 3164 KB Output is correct
6 Correct 45 ms 7608 KB Output is correct
7 Correct 1 ms 1880 KB Output is correct
8 Correct 66 ms 8772 KB Output is correct
9 Correct 67 ms 9268 KB Output is correct
10 Correct 84 ms 12472 KB Output is correct
11 Correct 1 ms 1884 KB Output is correct
12 Correct 1 ms 1884 KB Output is correct
13 Correct 1 ms 1880 KB Output is correct
14 Correct 83 ms 12224 KB Output is correct
15 Correct 69 ms 8520 KB Output is correct
16 Correct 81 ms 12064 KB Output is correct
17 Correct 1 ms 1884 KB Output is correct
18 Correct 1 ms 1880 KB Output is correct
19 Correct 1 ms 1884 KB Output is correct
20 Correct 91 ms 12276 KB Output is correct
21 Correct 1 ms 1880 KB Output is correct
22 Correct 1 ms 1884 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 2024 KB Output is correct
3 Correct 1 ms 1880 KB Output is correct
4 Correct 2 ms 2028 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1880 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 65 ms 6640 KB Output is correct
3 Correct 60 ms 6732 KB Output is correct
4 Correct 79 ms 9168 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 65 ms 6640 KB Output is correct
3 Correct 60 ms 6732 KB Output is correct
4 Correct 79 ms 9168 KB Output is correct
5 Correct 82 ms 10384 KB Output is correct
6 Correct 90 ms 11796 KB Output is correct
7 Correct 78 ms 11968 KB Output is correct
8 Correct 78 ms 11572 KB Output is correct
9 Correct 60 ms 7556 KB Output is correct
10 Correct 76 ms 11484 KB Output is correct
11 Correct 76 ms 11204 KB Output is correct
12 Correct 60 ms 7744 KB Output is correct
13 Correct 63 ms 8376 KB Output is correct
14 Correct 64 ms 8592 KB Output is correct
15 Correct 64 ms 8576 KB Output is correct
16 Correct 3 ms 2136 KB Output is correct
17 Correct 45 ms 7864 KB Output is correct
18 Correct 61 ms 7912 KB Output is correct
19 Correct 61 ms 7816 KB Output is correct
20 Correct 76 ms 11216 KB Output is correct
21 Correct 75 ms 11056 KB Output is correct
22 Correct 77 ms 11152 KB Output is correct