답안 #109385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109385	2019-05-06T10:10:16 Z	nvmdava	자동 인형 (IOI18_doll)	C++17	16 / 100	1000 ms	15668 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int> aft[200005], C, X, Y, st;
int sz = 0;
int t;

void go(int id, int root, int v, int cnt, int dep){
	dep--;
	if(dep == 0){
		if(cnt == 1){
			X[-1 - v] = 1;
			Y[-1 - v] = root;
		} else if(cnt == 2){
			X[-1 - v] = 1;
			Y[-1 - v] = 1;
		}
		
		return;
	}
	X[-1 - v] = --sz;
	Y[-1 - v] = cnt - (1 << dep) > 0 ? --sz : root;
	swap(X[-1 - v], Y[-1 - v]);
	X.pb(0);
	Y.pb(0);
	st.pb(0);
	go(id, root, Y[-1 - v], min(1 << dep, cnt), dep);
	if(X[-1 - v] != root){
		st.pb(0);
		X.pb(0);
		Y.pb(0);
		go(id, root, X[-1 - v], cnt - (1 << dep), dep);
	}
}

void trav(int root, int id, int idd){
	if(st[-1 - id] == 0){
		if(X[-1 - id] == 1){
			st[-1 - id] = 1;
			X[-1 - id] = aft[idd][t++];
			if(t == aft[idd].size()) return;
			trav(root, root, idd);
		} else {
			st[-1 - id] = 1;
			trav(root, X[-1 - id], idd);
		}
	} else {
		if(Y[-1 - id] == 1){
			st[-1 - id] = 0;
			Y[-1 - id] = aft[idd][t++];
			if(t == aft[idd].size()) return;
			trav(root, root, idd);
		} else {
			st[-1 - id] = 0;
			trav(root, Y[-1 - id], idd);
		}
	}
}

void solve(int id){
	if(!aft[id].size())
		C[id] = 0;
	else if(aft[id].size() == 1)
		C[id] = aft[id][0];
	else {
		t = 0;
		C[id] = --sz;
		X.pb(0);
		st.pb(0);
		Y.pb(0);
		int dep = ceil(log2(aft[id].size()));
		go(id, C[id], C[id], aft[id].size(), dep);
		trav(C[id], C[id], id);
	}
}

void create_circuit(int M, vector<int> A) {
	C.resize(M + 1);
	aft[0].pb(A[0]);
	for(int i = 1; i < A.size(); i++)
		aft[A[i - 1]].pb(A[i]);
	aft[A.back()].pb(0);
	for(int i = 0; i <= M; i++)
		solve(i);
	answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void trav(int, int, int)':
doll.cpp:42:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    if(t == aft[idd].size()) return;
      |       ~~^~~~~~~~~~~~~~~~~~
doll.cpp:52:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    if(t == aft[idd].size()) return;
      |       ~~^~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i = 1; i < A.size(); i++)
      |                 ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	4940 KB	Output is correct
2	Correct	57 ms	8652 KB	Output is correct
3	Correct	40 ms	8268 KB	Output is correct
4	Correct	4 ms	4940 KB	Output is correct
5	Correct	16 ms	6092 KB	Output is correct
6	Correct	60 ms	9992 KB	Output is correct
7	Correct	4 ms	4940 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	4940 KB	Output is correct
2	Correct	57 ms	8652 KB	Output is correct
3	Correct	40 ms	8268 KB	Output is correct
4	Correct	4 ms	4940 KB	Output is correct
5	Correct	16 ms	6092 KB	Output is correct
6	Correct	60 ms	9992 KB	Output is correct
7	Correct	4 ms	4940 KB	Output is correct
8	Correct	64 ms	10896 KB	Output is correct
9	Correct	88 ms	11168 KB	Output is correct
10	Correct	116 ms	13880 KB	Output is correct
11	Correct	5 ms	4940 KB	Output is correct
12	Correct	5 ms	4940 KB	Output is correct
13	Correct	6 ms	4940 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	4940 KB	Output is correct
2	Correct	57 ms	8652 KB	Output is correct
3	Correct	40 ms	8268 KB	Output is correct
4	Correct	4 ms	4940 KB	Output is correct
5	Correct	16 ms	6092 KB	Output is correct
6	Correct	60 ms	9992 KB	Output is correct
7	Correct	4 ms	4940 KB	Output is correct
8	Correct	64 ms	10896 KB	Output is correct
9	Correct	88 ms	11168 KB	Output is correct
10	Correct	116 ms	13880 KB	Output is correct
11	Correct	5 ms	4940 KB	Output is correct
12	Correct	5 ms	4940 KB	Output is correct
13	Correct	6 ms	4940 KB	Output is correct
14	Correct	137 ms	15668 KB	Output is correct
15	Correct	85 ms	10284 KB	Output is correct
16	Correct	116 ms	13056 KB	Output is correct
17	Correct	4 ms	4940 KB	Output is correct
18	Correct	4 ms	4940 KB	Output is correct
19	Correct	4 ms	4940 KB	Output is correct
20	Correct	144 ms	14608 KB	Output is correct
21	Correct	4 ms	4952 KB	Output is correct
22	Correct	8 ms	4940 KB	Output is correct