Submission #422948

#	Time	Username	Problem	Language	Result	Execution time	Memory
422948		alishahali1382	Mechanical Doll (IOI18_doll)	C++14	6 / 100	103 ms	22632 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
#pragma GCC optimize ("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, pii> pi4;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<", "; cerr<<"\n";}
#define pb push_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()

const int inf=1000001000; // 1e9
const ll INF=10000000010000000ll; // 1e16
const int mod=1000000007;
const int MAXN=300010, LOG=18;

int n, m, k, s;
vi C, X, Y;
vi shit[MAXN];

int Build(vi vec){
	if (SZ(vec)==1){
		return vec[0];
	}
	int v=++s;
	X.pb(inf);
	Y.pb(inf);
	vector<int> vec0, vec1;
	if (SZ(vec)&1) vec0.pb(-v);
	for (int x:vec){
		if (SZ(vec0)==SZ(vec1)) vec0.pb(x);
		else vec1.pb(x);
	}
	X[v-1]=Build(vec0);
	Y[v-1]=Build(vec1);
	// debugv(vec)
	// debug(-v)
	return -v;
}

void create_circuit(int _m, vi A){
	m=_m;
	n=SZ(A);
	for (int i=1; i<n; i++) shit[A[i-1]].pb(A[i]);
	shit[A.back()].pb(0);
	C.resize(m+1, 0);
	C[0]=A[0];
	for (int i=1; i<=m; i++) if (shit[i].size()) C[i]=Build(shit[i]);
	answer(C, X, Y);
	// debugv(C)
	// debugv(X)
	// debugv(Y)
}

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