Submission #816977

#	Time	Username	Problem	Language	Result	Execution time	Memory
816977		Jarif_Rahman	Mechanical Doll (IOI18_doll)	C++17	47 / 100	87 ms	13612 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const int inf = 1e7;

void create_circuit(int m, vector<int> A){
    int n = A.size();
    int k = 1;
    while(k < n) k*=2;

    vector<int> sth(2*k);
    vector<pair<int, int>> candidates;
    for(int i = k; i < 2*k; i++){
        int j = i, pos = 0;
        while(j != 1){
            if(j&1) pos++;
            pos<<=1;
            j>>=1;
        }
        pos>>=1;
        if(2*k-i-1 < n) candidates.pb({pos, i});
        sth[i] = -inf;
    }

    sort(candidates.begin(), candidates.end());
    for(int i = 1; i < n; i++) sth[candidates[i-1].sc] = A[i];
    sth[candidates.back().sc] = 0;

    vector<int> C, X, Y;

    for(int i = k-1; i >= 1; i--){
        if(sth[2*i] < 0 && sth[2*i+1] < 0){
            X.pb(-inf);
            Y.pb(-inf);
            sth[i] = -int(X.size());
        }
        else{
            int a = sth[2*i], b = sth[2*i+1];
            if(a >= inf) a = -(a-inf);
            if(b >= inf) b = -(b-inf);
            X.pb(a);
            Y.pb(b);
            sth[i] = inf+X.size();
        }
    }

    int st = -int(X.size());
    for(int &x: X) if(x == -inf) x = st;
    for(int &x: Y) if(x == -inf) x = st;

    C.assign(m+1, st);
    C[0] = A[0];

    answer(C, X, Y);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56