제출 #221817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
221817		patrikpavic2	자동 인형 (IOI18_doll)	C++17	100 / 100	179 ms	13724 KiB

doll

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  doll
* score: 100.0
* date:  2019-07-21 08:52:24.941918
*/
#include "doll.h"
#include <cstdio>

#define PB push_back

using namespace std;

typedef vector < int > vi;

const int N = 1e6 + 500;
const int M = 5e5 + 500;

int L[N], R[N], P[N], izb[N], por[N], fl[N], off, koj[N];

void poredaj(){
	int cur = 1, cnt = 0;
	while(cur != 0){
		fl[cur] = !fl[cur];
		if(fl[cur]) cur = L[cur];
		else cur = R[cur];
		//printf("cur = %d\n", cur);
		if(cur >= off){
			koj[cnt] = cur & 1;
			//printf("cnt %d cur %d gdje %d LR %d\n", cnt, cur, cur / 2, cur & 1);
			por[cnt++] = cur / 2;
			cur = 1;
		}
	}
}

void create_circuit(int m, vi a) {
	off = 1; int n = (int)a.size();
	while(2 * off <= n) off *= 2;
	off *= 2;
	for(int i = 1;i < off;i++){
		L[i] = 2 * i; R[i] = 2 * i + 1;
	}
	//printf("off = %d, %d\n", off, n <= off / 2);
	int barem = 2 * off - 1 - (n - off / 2);
	for(int i = 1;i < off;i++){
		if(L[i] >= off){
			if(L[i] - off >= n && n <= off / 2) L[i] = 1;
			if((n <= off / 2 && L[i] >= off + off / 2) || (n > off / 2 && L[i] < barem && L[i] >= off + off / 2)) L[i] = 1;

		}
		if(R[i] >= off){
			if(R[i] - off >= n && n <= off / 2) R[i] = 1;
			if((n <= off / 2 && R[i] >= off + off / 2) || (n > off / 2 && R[i] < barem && R[i] >= off + off / 2)) R[i] = 1;
		}
		//printf("%d => %d %d\n", i, L[i], R[i]);
	}
	//printf("barem %d\n", 2 * off - 1 - (n - off / 2));
	R[off - 1] = 0;
	poredaj();
	R[off - 1] = off;
	vi saz;
	for(int i = off - 1;i >= 0;i--){
		if(L[i] == 1 && R[i] == 1){
			izb[i] = 1;
			if(i & 1) R[i / 2] = 1;
			else      L[i / 2] = 1;
		}
	}
	for(int i = 0;i < n;i++){
		if(koj[i]) R[por[i]] = off + a[i];
		else       L[por[i]] = off + a[i];
	}
	for(int i = 1;i < off;i++){
		if(izb[i]) continue;
		saz.PB(i);
	}
	vi C, X, Y;
	for(int i = 0;i <= m;i++){
		C.PB(-1);
	}	
	for(int i = 0;i < (int)saz.size();i++){
		if(L[saz[i]] >= off) X.PB(L[saz[i]] - off);
		else{
			int tmp = lower_bound(saz.begin(), saz.end(), L[saz[i]]) - saz.begin();
			X.PB(-(tmp + 1));
		}
		if(R[saz[i]] >= off) Y.PB(R[saz[i]] - off);
		else{
			int tmp = lower_bound(saz.begin(), saz.end(), R[saz[i]]) - saz.begin();
			Y.PB(-(tmp + 1));
		}			
	}
//	printf("%d %d %d\n", n, (int)X.size(), (int)Y.size());
//	for(int i = 0;i <= m;i++)
//		printf("%d => %d\n", i, C[i]);
//	for(int i = 0;i < (int)X.size();i++)
//		printf("-%d => X %d Y %d\n", i + 1, X[i], Y[i]);
	answer(C, X, Y);
}

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