oj.uz

Submission #97071

# Submission time Handle Problem Language Result Execution time Memory
97071 2019-02-13T17:24:14 Z dlalswp25 Mechanical Doll (IOI18_doll) C++14
100 / 100
 141 ms 13168 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> C, X, Y, A;
int N, M;
int id;

int x[202020];
int y[202020];
int s[202020];

int mid = 0;

int build2k(int b) {
    int now = ++id;
    if(b == 2) {
        x[now] = y[now] = -1; return now;
    }
    x[now] = build2k(b / 2);
    y[now] = build2k(b / 2);
    return now;
}

int build(int n, int b) {
    //printf("%d %d\n", n, b);
    int now = ++id;
    
    if(n == 1 && b == 1) {
        x[now] = 1;
        y[now] = -1;
        return now;
    }
    if(n == b) {
        x[now] = 1;
        y[now] = build2k(b);
        return now;
    }
    if(n < b) {
        x[now] = 1;
        y[now] = build(n, b / 2);
        return now;
    }
    x[now] = build2k(b);
    y[now] = build(n - b, b / 2);
    return now;
}

void simu() {
    int now = 1;
    while(1) {
        s[now] = !s[now];
        if(!s[now]) { /// y
            if(y[now] == -1) {
                --mid;
                if(mid < -N + 1) { y[now] = 0; return; }
                else y[now] = -A[-mid - 1];
                now = 1;
            }
            else now = y[now];
        }
        else { /// x
            if(x[now] == -1) {
                --mid;
                if(mid < -N + 1) { x[now] = 0; return; }
                else x[now] = -A[-mid - 1];
                now = 1;
            }
            else now = x[now];
        }
    }
}

void create_circuit(int _M, std::vector<int> _A) {
    _A.push_back(0);
    A = _A;
    N = A.size();
    M = _M;
    
    if(N == 2) {
        C.resize(M + 1);
        C[0] = C[A[0]] = -1;
        X.push_back(A[0]);
        Y.push_back(0);
        answer(C, X, Y);
        return;
    }
    
    int b = 1; while(b * 2 <= N) b <<= 1;
    build(N, b);
    simu();
    
    for(int i = 0; i <= M; i++) C.push_back(-1);
    for(int i = 1; i <= id; i++) {
        X.push_back(-x[i]);
        Y.push_back(-y[i]);
    }
    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 49 ms 5292 KB Output is correct
3 Correct 65 ms 5160 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 68 ms 7400 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 49 ms 5292 KB Output is correct
3 Correct 65 ms 5160 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 68 ms 7400 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 85 ms 8876 KB Output is correct
9 Correct 93 ms 9252 KB Output is correct
10 Correct 129 ms 13168 KB Output is correct
11 Correct 2 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 49 ms 5292 KB Output is correct
3 Correct 65 ms 5160 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 68 ms 7400 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 85 ms 8876 KB Output is correct
9 Correct 93 ms 9252 KB Output is correct
10 Correct 129 ms 13168 KB Output is correct
11 Correct 2 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 131 ms 12796 KB Output is correct
15 Correct 87 ms 8760 KB Output is correct
16 Correct 141 ms 12528 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 128 ms 12952 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 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 81 ms 7132 KB Output is correct
3 Correct 75 ms 7140 KB Output is correct
4 Correct 134 ms 10724 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 81 ms 7132 KB Output is correct
3 Correct 75 ms 7140 KB Output is correct
4 Correct 134 ms 10724 KB Output is correct
5 Correct 120 ms 12480 KB Output is correct
6 Correct 126 ms 11800 KB Output is correct
7 Correct 128 ms 11940 KB Output is correct
8 Correct 122 ms 11800 KB Output is correct
9 Correct 82 ms 7048 KB Output is correct
10 Correct 122 ms 11512 KB Output is correct
11 Correct 127 ms 11160 KB Output is correct
12 Correct 79 ms 7392 KB Output is correct
13 Correct 90 ms 8220 KB Output is correct
14 Correct 86 ms 7936 KB Output is correct
15 Correct 86 ms 8036 KB Output is correct
16 Correct 4 ms 552 KB Output is correct
17 Correct 79 ms 7716 KB Output is correct
18 Correct 82 ms 7376 KB Output is correct
19 Correct 87 ms 7384 KB Output is correct
20 Correct 122 ms 11568 KB Output is correct
21 Correct 116 ms 11040 KB Output is correct
22 Correct 120 ms 11164 KB Output is correct