oj.uz

Submission #278767

# Submission time Handle Problem Language Result Execution time Memory
278767 2020-08-21T20:45:52 Z doowey Mechanical Doll (IOI18_doll) C++14
100 / 100
 159 ms 10028 KB 
#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair

int n;

const int N = (int)2e5 + 10;
int x[N], y[N];
int flip[N];
int id = 1;
int p = 1;

int build(int l, int r){
    if(l >= r) return 0;
    if(r + n <= p - 1) return -1;
    int cur = id++;
    int mid = (l + r) / 2;
    x[cur] = build(l, mid);
    y[cur] = build(mid + 1, r);
    return -cur;
}

void put(int xv){
    int cur = -1;
    int real;
    int nx;
    while(1){
        real = -cur;
        if(flip[real]){
            nx = y[real];
            flip[real] = false;
            if(nx == 0){
                y[real] = xv;
                return;
            }
            else{
                cur = nx;
            }
        }
        else{
            nx = x[real];
            flip[real] = true;
            if(nx == 0){
                x[real] = xv;
                return;
            }
            else{
                cur = nx;
            }
        }
    }
}

void create_circuit(int M, vector<int> A) {
    n = A.size();
    if(n == 1){
        vector<int> cc;
        cc.push_back(A[0]);
        for(int i = 1; i <= M ; i ++ )
            cc.push_back(0);
        answer(cc, {}, {});
        return ;
    }
    while(p < n)
        p *= 2;
    build(0, p - 1);
    vector<int> C(M + 1);
    C[0] = A[0];
    for(int i = 1; i <= M; i ++ )
        C[i] = -1;
    for(int i = 1; i < n ; i ++ )
        put(A[i]);
    if(n % 2 == 1)
        put(-1);
    put(0);
    vector<int> xx, yy;
    for(int i = 1; i < id; i ++ ){
        xx.push_back(x[i]);
        yy.push_back(y[i]);
    }
    answer(C, xx, yy);
}

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 4532 KB Output is correct
3 Correct 52 ms 3908 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 82 ms 5964 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 4532 KB Output is correct
3 Correct 52 ms 3908 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 82 ms 5964 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 86 ms 6700 KB Output is correct
9 Correct 92 ms 7168 KB Output is correct
10 Correct 131 ms 10028 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 49 ms 4532 KB Output is correct
3 Correct 52 ms 3908 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 82 ms 5964 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 86 ms 6700 KB Output is correct
9 Correct 92 ms 7168 KB Output is correct
10 Correct 131 ms 10028 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 150 ms 9704 KB Output is correct
15 Correct 87 ms 6424 KB Output is correct
16 Correct 129 ms 9380 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 157 ms 9744 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 2 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 2 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 2 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 84 ms 6180 KB Output is correct
3 Correct 84 ms 5924 KB Output is correct
4 Correct 134 ms 9048 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 84 ms 6180 KB Output is correct
3 Correct 84 ms 5924 KB Output is correct
4 Correct 134 ms 9048 KB Output is correct
5 Correct 130 ms 9340 KB Output is correct
6 Correct 141 ms 9132 KB Output is correct
7 Correct 132 ms 9164 KB Output is correct
8 Correct 131 ms 9096 KB Output is correct
9 Correct 89 ms 5920 KB Output is correct
10 Correct 141 ms 8996 KB Output is correct
11 Correct 116 ms 8968 KB Output is correct
12 Correct 98 ms 5856 KB Output is correct
13 Correct 90 ms 6200 KB Output is correct
14 Correct 85 ms 6300 KB Output is correct
15 Correct 84 ms 6396 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 80 ms 5996 KB Output is correct
18 Correct 88 ms 6092 KB Output is correct
19 Correct 80 ms 5872 KB Output is correct
20 Correct 128 ms 8984 KB Output is correct
21 Correct 159 ms 9044 KB Output is correct
22 Correct 121 ms 8960 KB Output is correct