Submission #535426

#	Time	Username	Problem	Language	Result	Execution time	Memory
535426		mario05092929	Mechanical Doll (IOI18_doll)	C++14	100 / 100	120 ms	19032 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
typedef vector <ll> vecl;
using namespace std;
const int INF = 1e9;
int nam;
int c[1000005],g;
struct hap {int bit,wi,wh;};
vector <hap> sw;
int n,m,k;
int edge[1000005][2];

bool cmp(hap x,hap y) {
    return x.bit < y.bit;
}

void build(int x,int go,int bit) {
    if(!nam) return;
    c[x] = ++g;
    if(x*2 >= k) {
        edge[g][0] = edge[g][1] = -1;
        sw.push_back({bit,g,0});
        sw.push_back({bit+(1 << go),g,1});
        nam--;
        return;
    }
    build(x*2+1,go+1,bit+(1 << go)), build(x*2,go+1,bit);
    edge[c[x]][0] = (c[x*2] == -1 ? -1 : -c[x*2]);
    edge[c[x]][1] = (c[x*2+1] == -1 ? -1 :-c[x*2+1]);
}

void create_circuit(int M,vec A) {
    memset(c,-1,sizeof(c));
    n = A.size(), m = M;
    for(k = 1;k <= n;k *= 2);
    nam = n/2+1;
    build(1,0,0);
    sort(sw.begin(),sw.end(),cmp);
    for(int i = 0;i < n;i++) edge[sw[i].wi][sw[i].wh] = A[i];
    edge[sw.back().wi][sw.back().wh] = 0;
    vec le,ri;
    for(int i = 1;i <= g;i++) {
        le.push_back(edge[i][0]);
        ri.push_back(edge[i][1]);
    }
    answer(vector<int>(m+1,-1),le,ri);
}

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