oj.uz

Submission #587737

# Submission time Handle Problem Language Result Execution time Memory
587737 2022-07-02T09:47:55 Z alirezasamimi100 Mechanical Doll (IOI18_doll) C++17
100 / 100
 102 ms 10988 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

vector<int> X,Y,A;
int N;

int solve(int k, int j){
    int v=-(int)X.size()-1;
    if(A[(((N-1)>>j)<<j)+k]==-1){
        return -1;
    }
    if((1<<j)==N){
        return A[k];
    }
    X.pb(0);
    Y.pb(0);
    int x=solve(k,j+1),y=solve(k+(1<<j),j+1);
    X[-v-1]=x;
    Y[-v-1]=y;
    return v;
}


void create_circuit(int M, vector<int> wtf) {
    vector<int> C(M + 1, -2);
    if((int)wtf.size()==1){
        C[0]=wtf[0];
        C[wtf[0]]=0;
        answer(C,X,Y);
        return;
    }
    wtf.pb(0);
    C[0]=wtf[0];
    wtf.erase(wtf.begin());
    N = wtf.size();
    int x=1,p=0;
    while(x<N) x*=2,p++;
    vector<int> vec;
    for(int i=0; i<p; i++){
        if((x-N)>>i&1) vec.pb(i);
    }
    reverse(vec.begin(),vec.end());
    A.resize(x,0);
    int k=0,t=0;
    for(int i : vec){
        for(int j=0; j<(1<<i); j++){
            A[(j<<(p-i))|k]=-1;
        }
        k|=1<<(p-i-1);
    }
    N=x;
    for(int i=0; i<N; i++){
        if(A[i]==-1) continue;
        A[i]=wtf[t++];
    }
    X.pb(-1);
    Y.pb(-2);
    solve(0,0);
    answer(C, X, Y);
}

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 3948 KB Output is correct
3 Correct 25 ms 4460 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 13 ms 1364 KB Output is correct
6 Correct 48 ms 5980 KB Output is correct
7 Correct 1 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 3948 KB Output is correct
3 Correct 25 ms 4460 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 13 ms 1364 KB Output is correct
6 Correct 48 ms 5980 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 51 ms 6776 KB Output is correct
9 Correct 70 ms 7772 KB Output is correct
10 Correct 102 ms 10504 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 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 3948 KB Output is correct
3 Correct 25 ms 4460 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 13 ms 1364 KB Output is correct
6 Correct 48 ms 5980 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 51 ms 6776 KB Output is correct
9 Correct 70 ms 7772 KB Output is correct
10 Correct 102 ms 10504 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 79 ms 10108 KB Output is correct
15 Correct 39 ms 6888 KB Output is correct
16 Correct 59 ms 9952 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 77 ms 10352 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 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 1 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 38 ms 5828 KB Output is correct
3 Correct 48 ms 6120 KB Output is correct
4 Correct 54 ms 9124 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 38 ms 5828 KB Output is correct
3 Correct 48 ms 6120 KB Output is correct
4 Correct 54 ms 9124 KB Output is correct
5 Correct 60 ms 10892 KB Output is correct
6 Correct 101 ms 9624 KB Output is correct
7 Correct 62 ms 10988 KB Output is correct
8 Correct 62 ms 10668 KB Output is correct
9 Correct 40 ms 6680 KB Output is correct
10 Correct 68 ms 10588 KB Output is correct
11 Correct 59 ms 10280 KB Output is correct
12 Correct 51 ms 7000 KB Output is correct
13 Correct 39 ms 6396 KB Output is correct
14 Correct 41 ms 7480 KB Output is correct
15 Correct 60 ms 7652 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 37 ms 6848 KB Output is correct
18 Correct 40 ms 6732 KB Output is correct
19 Correct 49 ms 6952 KB Output is correct
20 Correct 90 ms 10372 KB Output is correct
21 Correct 59 ms 10200 KB Output is correct
22 Correct 78 ms 10292 KB Output is correct