oj.uz

Submission #525722

# Submission time Handle Problem Language Result Execution time Memory
525722 2022-02-12T16:09:52 Z byunjaewoo Mechanical Doll (IOI18_doll) C++17
100 / 100
 106 ms 15108 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
 
const int Nmax=200010;
int M, N, cnt, Size, A[Nmax];
int out[Nmax], X[2*Nmax], Y[2*Nmax];
bool st[Nmax];
vector<int> V[Nmax];
 
void DFS(int curr, int s, int e) {
    if(e-s==1) {
        X[-curr]=Y[-curr]=INT_MAX;
        if(s<=Size-N) X[-curr]=-1;
        return;
    }
    int m=(s+e)/2;
    if(m<=Size-N) X[-curr]=-1;
    else {
        X[-curr]=--cnt;
        DFS(X[-curr], s, m);
    }
    Y[-curr]=--cnt;
    DFS(Y[-curr], m+1, e);
}
 
void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    N=A.size();
    Size=(1<<(32-__builtin_clz(N-1)));
    out[0]=--cnt;
    DFS(out[0], 1, Size);
    for(int i=1; i<=N; i++) {
        for(int curr=-1; ; ) {
            st[-curr]^=1;
            if(!st[-curr]) {
                if(Y[-curr]==INT_MAX) {
                    Y[-curr]=A[i-1];
                    break;
                }
                curr=Y[-curr];
            }
            else {
                if(X[-curr]==INT_MAX) {
                    X[-curr]=A[i-1];
                    break;
                }
                curr=X[-curr];
            }
        }
    }
    vector<int> C, l, r;
    for(int i=0; i<=M; i++) C.push_back(-1);
    for(int i=1; i<=-cnt; i++) {
        l.push_back(X[i]); r.push_back(Y[i]);
    }
    answer(C, l, r);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 38 ms 9036 KB Output is correct
3 Correct 36 ms 8856 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 11 ms 6212 KB Output is correct
6 Correct 53 ms 10660 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 38 ms 9036 KB Output is correct
3 Correct 36 ms 8856 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 11 ms 6212 KB Output is correct
6 Correct 53 ms 10660 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 67 ms 11656 KB Output is correct
9 Correct 70 ms 12036 KB Output is correct
10 Correct 106 ms 14908 KB Output is correct
11 Correct 2 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 2 ms 4940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 38 ms 9036 KB Output is correct
3 Correct 36 ms 8856 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 11 ms 6212 KB Output is correct
6 Correct 53 ms 10660 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 67 ms 11656 KB Output is correct
9 Correct 70 ms 12036 KB Output is correct
10 Correct 106 ms 14908 KB Output is correct
11 Correct 2 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 2 ms 4940 KB Output is correct
14 Correct 101 ms 14528 KB Output is correct
15 Correct 65 ms 12028 KB Output is correct
16 Correct 102 ms 15108 KB Output is correct
17 Correct 2 ms 4940 KB Output is correct
18 Correct 2 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 101 ms 14716 KB Output is correct
21 Correct 2 ms 4940 KB Output is correct
22 Correct 2 ms 4940 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 62 ms 10160 KB Output is correct
3 Correct 61 ms 10220 KB Output is correct
4 Correct 91 ms 12980 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 62 ms 10160 KB Output is correct
3 Correct 61 ms 10220 KB Output is correct
4 Correct 91 ms 12980 KB Output is correct
5 Correct 98 ms 14952 KB Output is correct
6 Correct 97 ms 13564 KB Output is correct
7 Correct 96 ms 13676 KB Output is correct
8 Correct 97 ms 14328 KB Output is correct
9 Correct 61 ms 10172 KB Output is correct
10 Correct 93 ms 13264 KB Output is correct
11 Correct 91 ms 12980 KB Output is correct
12 Correct 60 ms 10192 KB Output is correct
13 Correct 64 ms 11620 KB Output is correct
14 Correct 66 ms 10608 KB Output is correct
15 Correct 63 ms 10720 KB Output is correct
16 Correct 4 ms 5196 KB Output is correct
17 Correct 58 ms 11500 KB Output is correct
18 Correct 61 ms 10300 KB Output is correct
19 Correct 61 ms 10196 KB Output is correct
20 Correct 92 ms 14192 KB Output is correct
21 Correct 94 ms 12932 KB Output is correct
22 Correct 93 ms 12940 KB Output is correct