oj.uz

Submission #422053

# Submission time Handle Problem Language Result Execution time Memory
422053 2021-06-09T16:21:25 Z Peti Mechanical Doll (IOI18_doll) C++14
100 / 100
 551 ms 11296 KB 
#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

std::vector<int> X, Y;

int add_switch(){
    X.push_back(0);
    Y.push_back(0);
    return (int)X.size()-1;
}

void set_child(int x, int l, int r){
    X[x] = l;
    Y[x] = r;
}

int get_reverse(int x, int log){
    int ret = 0;
    for(int i = log; i >= 0; i--)
        if(x&(1<<i))
            ret += (1<<(log-i));
    return ret;
}

int build(vector<int> &v, int l, int r, int n){
    if(n-(int)v.size() >= r)
        return -1;
    if(l+1 == r)
        return v[l-n+(int)v.size()];
    int m = (l+r)/2, x = add_switch();
    set_child(x, build(v, l, m, n), build(v, m, r, n));
    return -x-1;
}

void add(int x, vector<int> v){
    int n = (int)v.size();
    int log = 1;
    while((1<<log) < n)
        log++;

    vector<int> inds(n);

    iota(inds.begin(), inds.end(), (1<<log)-n);
    sort(inds.begin(), inds.end(), [&log](int a, int b){ return get_reverse(a, log-1) < get_reverse(b, log-1); });
    vector<int> v2(n);
    for(int i = 0; i < n; i++)
        v2[inds[i]-(1<<log)+n] = v[i];

    build(v2, 0, 1<<log, 1<<log);
    return;
}

void create_circuit(int M, std::vector<int> A) {
    int N = A.size();

    std::vector<int> C(M + 1, -1);
    A.push_back(0);
    add(0, A);

    //for(int i = 0; i < (int)X.size(); i++)
        //cout<<-i-1<<": "<<X[i]<<" "<<Y[i]<<"\n";

    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:56:9: warning: unused variable 'N' [-Wunused-variable]
   56 |     int N = A.size();
      |         ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 216 ms 4936 KB Output is correct
3 Correct 199 ms 4584 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 244 ms 6496 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 216 ms 4936 KB Output is correct
3 Correct 199 ms 4584 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 244 ms 6496 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 442 ms 7404 KB Output is correct
9 Correct 429 ms 7796 KB Output is correct
10 Correct 551 ms 11296 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 216 ms 4936 KB Output is correct
3 Correct 199 ms 4584 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 244 ms 6496 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 442 ms 7404 KB Output is correct
9 Correct 429 ms 7796 KB Output is correct
10 Correct 551 ms 11296 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 526 ms 10888 KB Output is correct
15 Correct 349 ms 7016 KB Output is correct
16 Correct 513 ms 10820 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 491 ms 10884 KB Output is correct
21 Correct 1 ms 332 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 296 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 460 ms 6512 KB Output is correct
3 Correct 423 ms 6524 KB Output is correct
4 Correct 521 ms 9820 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 460 ms 6512 KB Output is correct
3 Correct 423 ms 6524 KB Output is correct
4 Correct 521 ms 9820 KB Output is correct
5 Correct 531 ms 10696 KB Output is correct
6 Correct 475 ms 10648 KB Output is correct
7 Correct 518 ms 10732 KB Output is correct
8 Correct 478 ms 10532 KB Output is correct
9 Correct 378 ms 6508 KB Output is correct
10 Correct 485 ms 10404 KB Output is correct
11 Correct 475 ms 10144 KB Output is correct
12 Correct 419 ms 6768 KB Output is correct
13 Correct 443 ms 6948 KB Output is correct
14 Correct 434 ms 7088 KB Output is correct
15 Correct 453 ms 7144 KB Output is correct
16 Correct 8 ms 460 KB Output is correct
17 Correct 394 ms 6596 KB Output is correct
18 Correct 472 ms 6720 KB Output is correct
19 Correct 428 ms 6752 KB Output is correct
20 Correct 542 ms 10412 KB Output is correct
21 Correct 504 ms 10132 KB Output is correct
22 Correct 528 ms 10148 KB Output is correct