Submission #587094

#	Time	Username	Problem	Language	Result	Execution time	Memory
587094		jasmin	Mechanical Doll (IOI18_doll)	C++14	100 / 100	113 ms	13756 KiB

doll

#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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56