oj.uz

Submission #587094

# Submission time Handle Problem Language Result Execution time Memory
587094 2022-07-01T09:58:29 Z jasmin Mechanical Doll (IOI18_doll) C++14
100 / 100
 113 ms 13756 KB 
#include<bits/stdc++.h>
using namespace std;
#include<doll.h>
const int inf=1e9+7;

/*void answer(vector<int> c, vector<int> x, vector<int> y){
    cout << c.size() << "\n";
    for(auto e: c){
        cout << e << " ";
    }
    cout << "\n";
    cout << x.size() << "\n";
    for(int i=0; i<(int)x.size(); i++){
        cout << x[i] << " " << y[i] << "\n";
    }
}*/

int pow2(int x){
    int ans=1;
    while(ans<x){
        ans*=2;
    }
    return ans;
}

void make_tree(int v, int h, int n, vector<int>& num){
    if((1<<h)>=n) return;

    num[v*2+1]=num[v];
    num[v*2+2]=num[v]+(1<<h);
    make_tree(v*2+1, h+1, n, num);
    make_tree(v*2+2, h+1, n, num);
}

vector<int> x;
vector<int> y;
int ind=1;
int enumerate(int v, int h, int n, vector<int>& is){
    if((1<<h)>=n){
        return -is[v];
    }

    int child0=enumerate(v*2+1, h+1, n, is);
    int child1=enumerate(v*2+2, h+1, n, is);
    if(child0==-inf && child1==-inf){
        return -inf;
    }

    x.push_back(-child0);
    y.push_back(-child1);
    int i=ind;
    ind++;
    return i;
}

void create_circuit(int m, vector<int> a){
    a.push_back(0);
    int n=a.size();

    int p=pow2(n);
    vector<int> num(2*p, 0);
    make_tree(0, 0, n, num);

    vector<int> is(2*p, inf);
    //cout << p << "\n";
    vector<pair<int,int> > sorted;
    for(int i=2*p-2; i>=0 && (int)sorted.size()<n; i--){
        sorted.push_back({num[i], i});
    }
    sort(sorted.begin(), sorted.end());
    for(int i=0; i<n; i++){
        int v=sorted[i].second;
        is[v]=a[i];
        //cout << v << " (" << num[v] << ") " << a[i] << "\n";
    }

    int root=enumerate(0, 0, n, is);
    for(int i=0; i<(int)x.size(); i++){
        if(x[i]==inf) x[i]=-root;
        if(y[i]==inf) y[i]=-root;
    }
    vector<int> c(m+1, -root);
    answer(c, x, y);
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int m, n;
    cin >> m >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    create_circuit(m, a);
}*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 37 ms 6520 KB Output is correct
3 Correct 32 ms 6088 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 49 ms 7976 KB Output is correct
7 Correct 1 ms 300 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 37 ms 6520 KB Output is correct
3 Correct 32 ms 6088 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 49 ms 7976 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 63 ms 10612 KB Output is correct
9 Correct 65 ms 10980 KB Output is correct
10 Correct 113 ms 13756 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 37 ms 6520 KB Output is correct
3 Correct 32 ms 6088 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 49 ms 7976 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 63 ms 10612 KB Output is correct
9 Correct 65 ms 10980 KB Output is correct
10 Correct 113 ms 13756 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 109 ms 13292 KB Output is correct
15 Correct 58 ms 10192 KB Output is correct
16 Correct 108 ms 13240 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 1 ms 216 KB Output is correct
20 Correct 100 ms 13688 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 57 ms 10032 KB Output is correct
3 Correct 57 ms 9928 KB Output is correct
4 Correct 87 ms 12856 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 57 ms 10032 KB Output is correct
3 Correct 57 ms 9928 KB Output is correct
4 Correct 87 ms 12856 KB Output is correct
5 Correct 85 ms 12856 KB Output is correct
6 Correct 87 ms 12956 KB Output is correct
7 Correct 100 ms 12916 KB Output is correct
8 Correct 85 ms 12856 KB Output is correct
9 Correct 58 ms 9920 KB Output is correct
10 Correct 97 ms 12916 KB Output is correct
11 Correct 79 ms 12952 KB Output is correct
12 Correct 58 ms 9980 KB Output is correct
13 Correct 58 ms 9932 KB Output is correct
14 Correct 61 ms 9928 KB Output is correct
15 Correct 58 ms 9900 KB Output is correct
16 Correct 2 ms 568 KB Output is correct
17 Correct 71 ms 7876 KB Output is correct
18 Correct 64 ms 10024 KB Output is correct
19 Correct 73 ms 10016 KB Output is correct
20 Correct 87 ms 12924 KB Output is correct
21 Correct 82 ms 12924 KB Output is correct
22 Correct 101 ms 12840 KB Output is correct