oj.uz

Submission #96431

# Submission time Handle Problem Language Result Execution time Memory
96431 2019-02-09T12:49:24 Z someone_aa Mechanical Doll (IOI18_doll) C++17
100 / 100
 152 ms 11688 KB 
#include <bits/stdc++.h>
#include "doll.h"
#define pb push_back
using namespace std;
const int maxn = 300100;
int n, m;
int N, br; // N is the first power of two greater than n
int x[maxn], y[maxn];

int build_tree(int l, int r, int cnt) {
    int ind = br;
    br++;
    if(r == l + 1) {
        //cout<<l<<", "<<r<<" - "<<cnt<<"\n";
        if(cnt == 1) x[ind] = 1;
        return ind;
    }
    //cout<<l<<" "<<r<<" -> "<<ind<<" "<<cnt<<"\n";
    int tsize = r - l + 1;
    int mid = tsize / 2;
    if(cnt <= mid) {
        // build recursively right subtree
        // make left subtree go left
        int midpoint = (l+r)/2;
        x[ind] = 1;
        y[ind] = build_tree(midpoint+1, r, cnt);
    }
    else {
        // make all in right
        // everything that is left put in left subtree
        int midpoint = (l+r)/2;
        y[ind] = build_tree(midpoint+1, r, mid);
        x[ind] = build_tree(l, midpoint, cnt-mid);
    }
    return ind;
}

bool state[maxn];

int pntr_x[maxn];
int pntr_y[maxn];

void insert_point(int ind, int val, int l, int r) {

    if(r == l + 1) {
        // base case
        if(!state[ind]) {
            state[ind] = true;
            if(x[ind] == 0) {
                pntr_x[ind] = val;
            }
            else insert_point(x[ind], val, 0, N-1);
        }
        else {
            state[ind] = false;
            if(y[ind] == 0) {
                pntr_y[ind] = val;
            }
            else insert_point(y[ind], val, 0, N-1);
        }
        return;
    }
    else {
        state[ind] = !state[ind];
        int mid = (l + r) / 2;
        if(state[ind]) {
            // left

            if(x[ind] == 1) insert_point(x[ind], val, 0, N-1);
            else insert_point(x[ind], val, l, mid);
        }
        else {
            // right
            if(y[ind] == -1) insert_point(y[ind], val, 0, N-1);
            else insert_point(y[ind], val, mid+1, r);
        }
    }
}

void create_circuit(int M, std::vector<int> A) {
    A.pb(0);
    m = M; n = A.size();
    vector<int>C(M+1);
    for(int i=0;i<=M;i++) {
        C[i] = -1;
    }

    N = 1;
    while(N < n) {
        N *= 2;
    }
    br = 1;
    build_tree(0, N-1, n);

    vector<int>X, Y;

    for(int i=0;i<n;i++) {
        insert_point(1, A[i], 0, N-1);
    }


    for(int i=1;i<br;i++) {
        if(x[i] == 0) X.pb(pntr_x[i]);
        else X.pb(-x[i]);

        if(y[i] == 0) Y.pb(pntr_y[i]);
        else Y.pb(-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 53 ms 4788 KB Output is correct
3 Correct 44 ms 4972 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 68 ms 7108 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 4788 KB Output is correct
3 Correct 44 ms 4972 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 68 ms 7108 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 85 ms 7656 KB Output is correct
9 Correct 117 ms 8136 KB Output is correct
10 Correct 127 ms 11688 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 4788 KB Output is correct
3 Correct 44 ms 4972 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 68 ms 7108 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 85 ms 7656 KB Output is correct
9 Correct 117 ms 8136 KB Output is correct
10 Correct 127 ms 11688 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 152 ms 11160 KB Output is correct
15 Correct 92 ms 7132 KB Output is correct
16 Correct 125 ms 10868 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 134 ms 11620 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 332 KB Output is correct
2 Correct 80 ms 6616 KB Output is correct
3 Correct 74 ms 6548 KB Output is correct
4 Correct 115 ms 9820 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 80 ms 6616 KB Output is correct
3 Correct 74 ms 6548 KB Output is correct
4 Correct 115 ms 9820 KB Output is correct
5 Correct 131 ms 10792 KB Output is correct
6 Correct 125 ms 10420 KB Output is correct
7 Correct 125 ms 10476 KB Output is correct
8 Correct 122 ms 10236 KB Output is correct
9 Correct 74 ms 6528 KB Output is correct
10 Correct 144 ms 10104 KB Output is correct
11 Correct 119 ms 9816 KB Output is correct
12 Correct 79 ms 6520 KB Output is correct
13 Correct 84 ms 6808 KB Output is correct
14 Correct 82 ms 6944 KB Output is correct
15 Correct 82 ms 7108 KB Output is correct
16 Correct 3 ms 564 KB Output is correct
17 Correct 72 ms 7880 KB Output is correct
18 Correct 76 ms 6512 KB Output is correct
19 Correct 80 ms 6512 KB Output is correct
20 Correct 127 ms 9976 KB Output is correct
21 Correct 117 ms 9820 KB Output is correct
22 Correct 118 ms 9904 KB Output is correct