oj.uz

Submission #75888

# Submission time Handle Problem Language Result Execution time Memory
75888 2018-09-11T12:54:55 Z kdh9949 Mechanical Doll (IOI18_doll) C++17
100 / 100
 207 ms 10616 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

static int n, m, q, v;
static vector<int> a, c, x, y, l, s;

void f(int z){
    x.push_back(-1);
    y.push_back(-1);
    l.push_back(!z);
    s.push_back(0);
    if(!z) return;
    int w = q;
    x[w - 1] = -(++q);
    f(z - 1);
    y[w - 1] = -(++q);
    f(z - 1);
}

void create_circuit(int M, vector<int> A) {
    n = A.size(); m = M; a = A;
    c = vector<int>(m + 1, -1);
    for(v = 1; (1 << (v - 1)) <= n; v++){
        x.push_back(-1);
        y.push_back(-(v + 1));
        l.push_back(0);
        s.push_back(0);
    }
    y[--v - 1] = 0;
    q = v;
    for(int i = v, j = 0; i >= 1; i--, j++){
        if(n & (1 << j)){
            if(!j) x[i - 1] = 1;
            else{
                x[i - 1] = -(++q);
                f(j - 1);
            }
        }
    }
    q = 0;
    for(int z = 1; z; ){
        s[z - 1] ^= 1;
        if(s[z - 1]){
            if(l[z - 1]){
                x[z - 1] = a[q++];
                z = 1;
            }
            else if(x[z - 1] == 1){
                x[z - 1] = a[q++];
                z = 1;
            }
            else z = -x[z - 1];
        }
        else{
            if(l[z - 1]){
                y[z - 1] = a[q++];
                z = 1;
            }
            else z = -y[z - 1];
        }
    }
    answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 56 ms 4768 KB Output is correct
3 Correct 52 ms 4564 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1388 KB Output is correct
6 Correct 84 ms 5864 KB Output is correct
7 Correct 1 ms 256 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 56 ms 4768 KB Output is correct
3 Correct 52 ms 4564 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1388 KB Output is correct
6 Correct 84 ms 5864 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 114 ms 8016 KB Output is correct
9 Correct 106 ms 8628 KB Output is correct
10 Correct 207 ms 10616 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 56 ms 4768 KB Output is correct
3 Correct 52 ms 4564 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1388 KB Output is correct
6 Correct 84 ms 5864 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 114 ms 8016 KB Output is correct
9 Correct 106 ms 8628 KB Output is correct
10 Correct 207 ms 10616 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 147 ms 10124 KB Output is correct
15 Correct 96 ms 7576 KB Output is correct
16 Correct 168 ms 9948 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 154 ms 10412 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 204 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 1 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 97 ms 6624 KB Output is correct
3 Correct 92 ms 6648 KB Output is correct
4 Correct 162 ms 8992 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 97 ms 6624 KB Output is correct
3 Correct 92 ms 6648 KB Output is correct
4 Correct 162 ms 8992 KB Output is correct
5 Correct 162 ms 9768 KB Output is correct
6 Correct 143 ms 9436 KB Output is correct
7 Correct 144 ms 9556 KB Output is correct
8 Correct 146 ms 9196 KB Output is correct
9 Correct 101 ms 6592 KB Output is correct
10 Correct 146 ms 9228 KB Output is correct
11 Correct 156 ms 8988 KB Output is correct
12 Correct 100 ms 6788 KB Output is correct
13 Correct 103 ms 7272 KB Output is correct
14 Correct 99 ms 7264 KB Output is correct
15 Correct 118 ms 7500 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 91 ms 6092 KB Output is correct
18 Correct 96 ms 6744 KB Output is correct
19 Correct 140 ms 6808 KB Output is correct
20 Correct 182 ms 9108 KB Output is correct
21 Correct 166 ms 8988 KB Output is correct
22 Correct 192 ms 8976 KB Output is correct