oj.uz

Submission #92077

# Submission time Handle Problem Language Result Execution time Memory
92077 2019-01-01T11:45:55 Z Retro3014 Mechanical Doll (IOI18_doll) C++17
100 / 100
 169 ms 11172 KB 
#include "doll.h"
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> X, Y;
vector<int> type;
int N, K;

int idx(int x){
    return -x-1;
}

void dfs(int x, int y){
    int k=y/2;
    if(K-k >= N){
        K-=k;
        X[idx(x)]=-1;
    }else{
        if(k==1){
            X[idx(x)]=0;
        }
        else{
            X[idx(x)]=-((int)X.size()+1);
            X.push_back(0); Y.push_back(0); type.push_back(0);
        }
    }
    if(k==1){
        Y[idx(x)]=0;
    }else{
        Y[idx(x)]=-((int)X.size()+1);
        X.push_back(0); Y.push_back(0); type.push_back(0);
    }
    if(X[idx(x)]!=0 && X[idx(x)]!=-1)    dfs(X[idx(x)], k);
    if(Y[idx(x)]!=0 && Y[idx(x)]!=-1)    dfs(Y[idx(x)], k);
}

void dfs2(int x, int y){
    if(type[idx(x)]==0){
        type[idx(x)]=1;
        if(X[idx(x)]==0){
            X[idx(x)]=y;
            return;
        }else{
            dfs2(X[idx(x)], y);
            return;
        }
        
    }else{
        type[idx(x)]=0;
        if(Y[idx(x)]==0){
            Y[idx(x)]=y;
            return;
        }else{
            dfs2(Y[idx(x)], y);
            return;
        }
    }
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    N = (int)A.size();
    int two=1; while(two<N) two*=2;
    K = two;
    if(N==1){
        vector<int> C(M+1);
        C[0]=A[0];
        for(int i=1; i<=M; i++){
            C[i]=0;
        }
        vector<int> XY(0);
        answer(C, XY, XY);
        return;
    }
    X.push_back(0); Y.push_back(0); type.push_back(0);
    dfs(-1, two);
    for(int i=0; i<N; i++){
        dfs2(-1, A[i]);
    }
    vector<int> C(M+1);
    for(int i=0; i<=M; i++){
        C[i]=-1;
    }
    answer(C, X, Y);
    return;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 53 ms 3872 KB Output is correct
3 Correct 56 ms 4032 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 70 ms 6300 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 53 ms 3872 KB Output is correct
3 Correct 56 ms 4032 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 70 ms 6300 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 104 ms 6964 KB Output is correct
9 Correct 106 ms 7484 KB Output is correct
10 Correct 169 ms 11172 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 53 ms 3872 KB Output is correct
3 Correct 56 ms 4032 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 70 ms 6300 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 104 ms 6964 KB Output is correct
9 Correct 106 ms 7484 KB Output is correct
10 Correct 169 ms 11172 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 132 ms 10596 KB Output is correct
15 Correct 101 ms 6460 KB Output is correct
16 Correct 136 ms 10148 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 136 ms 10728 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 87 ms 5560 KB Output is correct
3 Correct 93 ms 5540 KB Output is correct
4 Correct 119 ms 8900 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 87 ms 5560 KB Output is correct
3 Correct 93 ms 5540 KB Output is correct
4 Correct 119 ms 8900 KB Output is correct
5 Correct 131 ms 10008 KB Output is correct
6 Correct 125 ms 9740 KB Output is correct
7 Correct 132 ms 9756 KB Output is correct
8 Correct 139 ms 9636 KB Output is correct
9 Correct 87 ms 5536 KB Output is correct
10 Correct 125 ms 9424 KB Output is correct
11 Correct 117 ms 9252 KB Output is correct
12 Correct 92 ms 5816 KB Output is correct
13 Correct 90 ms 6200 KB Output is correct
14 Correct 91 ms 6304 KB Output is correct
15 Correct 92 ms 6460 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 76 ms 6348 KB Output is correct
18 Correct 95 ms 5804 KB Output is correct
19 Correct 104 ms 5840 KB Output is correct
20 Correct 130 ms 9480 KB Output is correct
21 Correct 131 ms 9204 KB Output is correct
22 Correct 120 ms 9304 KB Output is correct