제출 #422962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422962		alishahali1382	자동 인형 (IOI18_doll)	C++14	53 / 100	216 ms	22608 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){
	// assert(vec.size());
	if (SZ(vec)==1){
		// debugv(vec)
		// cerr<<"\n";
		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);
	}
	
	// debugv(vec)
	// debugv(vec0)
	// debugv(vec1)
	// debug(-v)
	// cerr<<"\n\n";

	int x=Build(vec0);
	int y=Build(vec1);
	X[v-1]=x;
	Y[v-1]=y;
	
	// debugv(vec)
	// debug(-v)
	// debugv(X)
	// debugv(Y)
	// cerr<<"\n\n";

	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: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56