Submission #295115

#	Time	Username	Problem	Language	Result	Execution time	Memory
295115		shayan_p	Mechanical Doll (IOI18_doll)	C++17	0 / 100	1 ms	204 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 = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<pii> vec;

int solve(vector<int> v){
    if(sz(v) == 1){
	return v[0];
    }
    vector<int> v1, v2;
    for(int i = 0; i < sz(v); i++){
	if(i & 1)
	    v2.PB(v[i]);
	else
	    v1.PB(v[i]);
    }
    if(sz(v1) == sz(v2)){
	vec.PB({solve(v1), solve(v2)});
	return -sz(vec);
    }
    else{
	swap(v1[sz(v1)-1], v2[sz(v2)-1]);

	vec.PB({-1, -1});
	int root = sz(vec);

	int A = solve(v1);
	int &x = v2[sz(v2)-1];
	vec.PB({-root, x});
	x = -sz(vec);

	int B = solve(v2);

	vec[root-1] = {A, B};

	return root;
    }
    assert(0);
}

void create_circuit(int M, vector<int> A) {
    A.PB(0);
    int st = solve(A);
    vector<int> C, X, Y;
    for(int i = 0; i <= M; i++){
	C.PB(st);
    }
    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: 0 / 18
• Subtask 6: 0 / 56