제출 #299785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299785		cfalas	Mechanical Doll (IOI18_doll)	C++14	15 / 100	356 ms	25956 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>

using namespace std;

#define FORi(i,a,b) for(int i=a;i<b;i++)
#define FOR(i,n) FORi(i,0,n)
#define FOA(v,n) for(auto v : n)
#define len(a) ((int)a.size())
typedef vector<int> vi;

map<int, vi> points;
bool vis[100000];
vi X,Y,c;

#define neg(v) (-v-1)
#define MOD 10000000
#define MID ((l+r)/2)

void make(int pos, int l, int r){
	if(l+1>=r) return;
	int a1 = len(X);
	int a2 = len(X)+1;
	X.push_back(MOD);
	X.push_back(MOD);
	Y.push_back(MOD);
	Y.push_back(MOD);
	X[pos] = neg(a1);
	Y[pos] = neg(a2);
	make(a1, l, MID);
	make(a2, MID+1, r);
}

void rec(int cur){
	////cout<<"Recursing "<<cur<<endl;
	vis[cur] = true;

	int req_level = ceil(log2(len(points[cur])));
	////cout<<"LEVELS "<<cur<<" "<<len(points[cur])<<endl;
	if(cur>0 && len(points[cur]) && req_level){
		int org = len(X);
		c[cur] = neg(org);
		X.push_back(MOD);
		Y.push_back(MOD);
		//FOR(i,len(X)) cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;
		//cout<<endl;
		int min_needed = 1<<req_level;
		make(org, 0, min_needed-1);
		//FOR(i,len(X)) cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;
		//cout<<endl;
		points[cur].insert(points[cur].begin(), min_needed - len(points[cur]), neg(org));
		//cout<<"points: ";
		//FOA(v,points[cur]) cout<<v<<" ";
		//cout<<endl;
		FOR(i,min_needed){
			int t = i;
			int cnt=req_level;
			int pos = org;
			//cout<<cnt<<endl;
			while(cnt>1){
				if(t%2) pos = -Y[pos]-1;
				else pos = -X[pos]-1;
				t/=2;
				cnt--;
				//cout<<i<< " "<<t<<" "<<pos<<endl;
			}
			//cout<<i<< " "<<t<<" "<<pos<<endl;
			int anss = neg(org);
			anss = points[cur][i];
			//cout<<anss<<endl;
			//assert(min_needed>=len(points[cur]));
			////if(min_needed>len(points[cur])+i) anss = points[cur][min_needed-len(points[cur])+i-1],cout<<"yeeting "<<anss<<endl;
			//cout<<anss<<endl;
			
			if(t%2) Y[pos] = anss;
			else X[pos] = anss;

			//FOR(i,len(X)) cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;
			//cout<<endl;
		}
		//FOR(i,len(X)) cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;
		//cout<<endl;
	}
	else c[cur] = points[cur][0];

	////cout<<"Recursing "<<cur<<endl;
	FOA(v,points[cur]) if(!vis[v] && v>=0) rec(v);

}

void create_circuit(int M, std::vector<int> A) {
	c.resize(M+1);
	A.push_back(0);
	int prev=0;
	points[0].push_back(A[0]);
	FOR(i,len(A)-1){
		points[A[i]].push_back(A[i+1]);
	}
	rec(0);
	//cout<<"---\n";
	//FOR(i,M+1) cout<<i<<" "<<c[i]<<endl;
	////FOR(i,len(X)) cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<endl;

	answer(c, X, Y);
}

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:94:6: warning: unused variable 'prev' [-Wunused-variable]
   94 |  int prev=0;
      |      ^~~~

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