Submission #859061

#	Time	Username	Problem	Language	Result	Execution time	Memory
859061		qin	Mechanical Doll (IOI18_doll)	C++17	100 / 100	94 ms	12612 KiB

doll

#ifdef LOCAL
#else
#include "doll.h"
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int inf = 2e09; ll infll = 2e18;
vector<int> X, Y;
int cur = 1;
void dfs(int x, int pref, int s, int e, vector<int> &t){
		int mid = (s+e)>>1;
		X.emplace_back(0), Y.emplace_back(0);
		if(mid < pref) X[x-1] = -1;
		else{
				if(s != mid) X[x-1] = -(++cur), dfs(cur, pref, s, mid, t);
				else X[x-1] = t[s];
		}
				if(mid+1 != e) Y[x-1] = -(++cur), dfs(cur, pref, mid+1, e, t);
				else Y[x-1] = t[e];
}
void create_circuit(int m, vector<int> A){
		A.emplace_back(0); int n = ssize(A);
		vector<int> c(m+1, -1);
		
		int base = 1, log = 0;
		while(base < n) base <<= 1, ++log;
		vector<int> t(base);
		for(int i = 0; i < base; ++i) t[i] = i;
		
		vector<int> tmp0, tmp1, where(base);
		for(int len = base; len > 2; len >>= 1){
				for(int p = 0; p < base; p += len){
						tmp0 = vector<int>(), tmp1 = vector<int>();
						for(int i = p; i < p+len; ++i) if(i&1) tmp1.emplace_back(t[i]);
													   else    tmp0.emplace_back(t[i]);
						for(int i = 0; i < len/2; ++i)   t[i+p] = tmp0[i];
						for(int i = len/2; i < len; ++i) t[i+p] = tmp1[i-len/2];
				}
		}
		for(int i = 0; i < base; ++i) where[t[i]] = i;
		vector<int> tmp;
		int pref = base-ssize(A);
		for(int i = base-ssize(A); i < base; ++i) tmp.emplace_back(t[i]);
		sort(tmp.begin(), tmp.end());
		for(int i = 0; i < base-ssize(A); ++i) t[i] = -1;
		for(int i = 0; i < ssize(A); ++i) t[where[tmp[i]]] = A[i]; 
		dfs(1, pref, 0, base-1, t);
		#ifdef LOCAL
		for(int i = 0; i < ssize(X); ++i) printf("%d %d\n", X[i], Y[i]);
		#else
		answer(c, X, Y);
		#endif
}
#ifdef LOCAL
int main(){
		int T = 1;
		for(++T; --T; ){
				int m, n; scanf("%d%d", &m, &n);
				vector<int> A(n);
				for(int i = 0; i < n; ++i) scanf("%d", &A[i]);
				create_circuit(m, A);
		}
		return 0;
}
#endif

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