Submission #295378

#	Time	Username	Problem	Language	Result	Execution time	Memory
295378		shayan_p	Mechanical Doll (IOI18_doll)	C++17	60.67 / 100	166 ms	14400 KiB

doll

#include<bits/stdc++.h>
#include "doll.h"
     
#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)
     
using namespace std;
     
typedef pair<int, int> pii;
typedef long long ll;
     
const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> pws;

vector<pii> vec;
int what[maxn];
int arr[maxn];

void solve(vector<int> inp, int lg, int rt){
    assert(!vec.empty());
    if(lg == 1){
	if(sz(inp) == 2)
	    vec[-rt-1] = {inp[0], inp[1]};
	else
	    vec[-rt-1] = {-1, inp[0]};
	return;
    }
    reverse(inp.begin(), inp.end());
    vector<int> v1, v2;
    while(sz(inp) > (1<<(lg-1))){
	v1.PB(inp.back());
	inp.pop_back();
    }
    v2 = inp;
    reverse(v2.begin(), v2.end());
    if(v1.empty()){
	vec[-rt-1].F = pws[lg-1];
    }
    else{
	vec.PB({-1, -1});
	int r = -sz(vec);
	vec[-rt-1].F = r;
	solve(v1, lg-1, r);
    }
    vec.PB({-1, -1});
    int r = -sz(vec);
    vec[-rt-1].S = r;
    solve(v2, lg-1, r);
}

void create_circuit(int M, vector<int> A) {
    A.PB(0);
    int N = sz(A);
    int extra = 0;
    while(__builtin_popcount(N + extra) != 1)
	extra++;
    vec.PB({-1, -1});
    pws.PB(-sz(vec));
    for(int i = 1; (1<<i) <= extra; i++){ // <=
	vec.PB({-i, -i});
	pws.PB(-sz(vec));
    }    
    int lg = __builtin_ctz(N + extra);
    for(int i = 0; i < (1<<lg); i++){
	for(int j = 0; j < lg; j++){
	    what[i]+= bit(i, j) << (lg-1-j);
	}
    }
    iota(arr, arr + N, 0);
    sort(arr, arr + N, [&](int i, int j){ return what[i + extra] < what[j + extra]; });

    vector<int> tdo(N);
    for(int i = 0; i < N; i++){
	tdo[arr[i]] = A[i];
    }
    solve(tdo, lg, -1);
    
    vector<int> C, X, Y;
    for(int i = 0; i <= M; i++){
    	C.PB(-1);
    }
    for(pii p : vec){
    	X.PB(p.F);
    	Y.PB(p.S);
    }
    answer(C, X, Y);
}

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