oj.uz

Submission #414408

# Submission time Handle Problem Language Result Execution time Memory
414408 2021-05-30T12:06:16 Z Temmie Mechanical Doll (IOI18_doll) C++17
100 / 100
 143 ms 12948 KB 
#include "doll.h"
#include <bits/stdc++.h>

//void answer(std::vector <int> c, std::vector <int> x, std::vector <int> y) {
	//std::cerr << "answered" << std::endl;
	//for (int i : c) std::cerr << i << " ";
	//std::cout << std::endl;
	//for (int i : x) std::cerr << i << " ";
	//std::cout << std::endl;
	//for (int i : y) std::cerr << i << " ";
	//std::cout << std::endl;
//}

int inf = 1 << 30;

std::vector <std::pair <int, int>> sw;
std::vector <int> c, x, y;
std::vector <int> dir;

void place(int node, int to_place) {
	//std::cerr << "<" << node << ", " << to_place << ">" << std::endl;
	int tir = dir[node];
	dir[node] ^= 1;
	if (tir == 0) {
		//left
		if (sw[node].first == inf) {
			sw[node].first = to_place;
			return;
		}
		//std::cerr << sw[node].first << std::endl;
		assert(sw[node].first <= 0);
		place(-sw[node].first, to_place);
		return;
	} else {
		//right
		if (sw[node].second == inf) {
			sw[node].second = to_place;
			return;
		}
		assert(sw[node].second <= 0);
		place(-sw[node].second, to_place);
		return;
	}
	assert(false);
}

void create_circuit(int m, std::vector <int> a) {
	int n = a.size();
	int size = 1;
	int depth = 0;
	while (size < n) {
		size <<= 1;
		depth++;
	}
	std::vector <int> layer;
	//std::cerr << "initial layer iteratons: " << ((n + 1) >> 1) << std::endl;
	for (int i = 0; i < ((n + 1) >> 1); i++) {
		sw.emplace_back(inf, inf *
		((n & 1) && i == ((n + 1) >> 1) - 1 ? -1 : 1));
		layer.push_back(i);
		//std::cerr << "initial layer: " << sw.back().first << " and " <<
		//sw.back().second << std::endl;
	}
	for (int i = 0; i < depth - 1; i++) {
		//std::cerr << "layer: ";
		//for (int j : layer) std::cerr << j << " ";
		//std::cerr << std::endl;
		std::vector <int> new_layer;
		for (int j = 0; j < (int)layer.size(); j += 2) {
			new_layer.push_back(sw.size());
			sw.emplace_back(-layer[j],
			j + 1 < (int)layer.size() ? -layer[j + 1] : -inf);
		}
		std::swap(layer, new_layer);
	}
	assert((int)layer.size() == 1);
	for (auto& p : sw) std::swap(p.first, p.second);
	int first = layer[0];
	//std::cerr << "first: " << first << std::endl;
	for (auto& p : sw) {
		if (p.first == -inf) {
			p.first = -first;
		}
		if (p.second == -inf) {
			p.second = -first;
		}
	}
	//for (auto p : sw) std::cerr << "(" << p.first << ", " << p.second << ")" << std::endl;
	c.resize(m + 1, -first);
	c[0] = a[0]; // this is 1 idx
	a.push_back(0);
	dir.resize(sw.size(), 0);
	//std::cerr << "a.size(): " << a.size() << std::endl;
	for (int i = 1; i < (int)a.size(); i++) {
		//std::cerr << "palce idx = " << i << " (" << a[i] << ")" << std::endl;
		place(first, a[i] + 1 /* this is 2 idx */);
	}
	for (int& i : c) if (i <= 0) i--; // make 1 idx
	for (auto p : sw) {
		//std::cerr << "p: (" << p.first << ", " << p.second << ")" << std::endl;
		x.push_back(p.first - 1);
		y.push_back(p.second - 1);
	}
	answer(c, x, y);
}

//int main() {
	
	//std::vector <int> a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
	//int m = 11;
	//create_circuit(m, a);
	
	//std::vector <int> a = { 1, 2, 1, 3 };
	//int m = 4;
	//create_circuit(m, a);
	
//}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 45 ms 5148 KB Output is correct
3 Correct 44 ms 5476 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1484 KB Output is correct
6 Correct 65 ms 7888 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 45 ms 5148 KB Output is correct
3 Correct 44 ms 5476 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1484 KB Output is correct
6 Correct 65 ms 7888 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 88 ms 8468 KB Output is correct
9 Correct 93 ms 9916 KB Output is correct
10 Correct 130 ms 12948 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 45 ms 5148 KB Output is correct
3 Correct 44 ms 5476 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1484 KB Output is correct
6 Correct 65 ms 7888 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 88 ms 8468 KB Output is correct
9 Correct 93 ms 9916 KB Output is correct
10 Correct 130 ms 12948 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 126 ms 12072 KB Output is correct
15 Correct 85 ms 8272 KB Output is correct
16 Correct 124 ms 11876 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 133 ms 12592 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 83 ms 6840 KB Output is correct
3 Correct 76 ms 7368 KB Output is correct
4 Correct 127 ms 10568 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 83 ms 6840 KB Output is correct
3 Correct 76 ms 7368 KB Output is correct
4 Correct 127 ms 10568 KB Output is correct
5 Correct 143 ms 11780 KB Output is correct
6 Correct 119 ms 11540 KB Output is correct
7 Correct 117 ms 11604 KB Output is correct
8 Correct 115 ms 11276 KB Output is correct
9 Correct 79 ms 7476 KB Output is correct
10 Correct 128 ms 11284 KB Output is correct
11 Correct 119 ms 10972 KB Output is correct
12 Correct 73 ms 7660 KB Output is correct
13 Correct 76 ms 7440 KB Output is correct
14 Correct 75 ms 8172 KB Output is correct
15 Correct 74 ms 8228 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 70 ms 7168 KB Output is correct
18 Correct 69 ms 7096 KB Output is correct
19 Correct 91 ms 7728 KB Output is correct
20 Correct 111 ms 11104 KB Output is correct
21 Correct 108 ms 10888 KB Output is correct
22 Correct 118 ms 10984 KB Output is correct