oj.uz

Submission #713767

# Submission time Handle Problem Language Result Execution time Memory
713767 2023-03-23T03:15:24 Z Foxyy Mechanical Doll (IOI18_doll) C++17
53 / 100
 258 ms 26816 KB 
#include <bits/stdc++.h>
using namespace std;

#include "doll.h"

const int INF = 0x3f3f3f3f;

struct Switch {
	int x, y;
};
vector<Switch> switches{{-INF, -INF}};
Switch& get_switch(int id) {
	return switches[-id];
}

int new_switch(int x, int y) {
	static int cnt = 0;
	cnt++;
	switches.push_back({x, y});
	return -cnt;
}

int create_switch_tree(int sz) {
//	cerr << "creating a switch tree of size: " << sz << '\n';
	if (sz == 0) {
		return INF;
	}
	if (sz == 1) {
		return new_switch(INF, INF);
	}
	sz--;
	int x = create_switch_tree((sz+1)/2);
	int y = create_switch_tree(sz/2);
	int id = new_switch(x, y);
//	cerr << get_switch(id).x << ' ' << get_switch(id).y << '\n';
//	cerr << id << ' ' << x << ' ' << y << '\n';
	return id;
}

//void print(int switch_id) {
//	cerr << "switch #" << switch_id << ": ";
//	auto [x, y] = get_switch(switch_id);
//	cerr << "x = " << x << ", ";
//	cerr << "y = " << y << '\n';
//	if (x < 0) {
//		print(x);
//	}
//	if (y < 0) {
//		print(y);
//	}
//}

void assign_value(int switch_tree_root, vector<int>& vec) {
//	cerr << "assigning " << (int)vec.size() << " values to a switch tree with root = " << switch_tree_root << '\n';
	
	map<int, pair<int, int>> mp;
	
	function<void(int, int, int)> dfs = [&](int switch_id, int val, int depth) {
		auto& current_switch = get_switch(switch_id);
		
		if (current_switch.x == INF) {
			mp[val] = {switch_id, 0};
		} else {
			dfs(current_switch.x, val, depth+1);
		}
		
		if (current_switch.y == INF) {
			mp[val + (1 << depth)] = {switch_id, 1};
		} else {
			dfs(current_switch.y, val + (1 << depth), depth+1);
		}
	};
	
	dfs(switch_tree_root, 0, 0);
	
	vector<pair<int, int>> leaves;
	for (auto [val, p] : mp) {
		leaves.push_back(p);
	}
	for (int i = 0; i < (int)vec.size()-1; i++) {
		auto [id, lr] = leaves[i];
		if (lr == 0) {
			get_switch(id).x = vec[i];
		} else {
			get_switch(id).y = vec[i];
		}
	}
	for (int i = (int)vec.size()-1; i < (int)leaves.size()-1; i++) {
		auto [id, lr] = leaves[i];
		if (lr == 0) {
			get_switch(id).x = switch_tree_root;
		} else {
			get_switch(id).y = switch_tree_root;
		}
	}
	auto [id, lr] = leaves.back();
	if (lr == 0) {
		get_switch(id).x = vec.back();
	} else {
		get_switch(id).y = vec.back();
	}
}

void create_circuit(int M, std::vector<int> A) {
	const int N = (int)A.size();
	vector<vector<int>> vec(M+1);
	for (int i = 0; i < N-1; i++) {
		vec[A[i]].push_back(A[i+1]);
	}
	vec[A.back()].push_back(0);
	
	vector<int> C(M+1, 0);
	C[0] = A[0];
	for (int i = 1; i <= M; i++) if (not vec[i].empty()) {
		if (vec[i].size() == 1) {
			C[i] = vec[i][0];
		} else {
			int sz = (int)vec[i].size()-1;
			sz = (1 << (__lg(sz)+1)) - 1;
			C[i] = create_switch_tree(sz);
//			print(C[i]);
			assign_value(C[i], vec[i]);
//			print(C[i]);
		}
	}
	
	vector<int> X((int)switches.size()-1);
	vector<int> Y((int)switches.size()-1);
	
	for (int i = 1; i < (int)switches.size(); i++) {
		X[i-1] = get_switch(-i).x;
		Y[i-1] = get_switch(-i).y;
	}
	
	answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 6324 KB Output is correct
3 Correct 21 ms 5204 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 51 ms 7724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 6324 KB Output is correct
3 Correct 21 ms 5204 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 51 ms 7724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 51 ms 7748 KB Output is correct
9 Correct 50 ms 8872 KB Output is correct
10 Correct 79 ms 11556 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 6324 KB Output is correct
3 Correct 21 ms 5204 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 51 ms 7724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 51 ms 7748 KB Output is correct
9 Correct 50 ms 8872 KB Output is correct
10 Correct 79 ms 11556 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 107 ms 13040 KB Output is correct
15 Correct 48 ms 6600 KB Output is correct
16 Correct 74 ms 9892 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 107 ms 11844 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 92 ms 12612 KB Output is correct
3 Partially correct 220 ms 23356 KB Output is partially correct
4 Partially correct 197 ms 24164 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 92 ms 12612 KB Output is correct
3 Partially correct 220 ms 23356 KB Output is partially correct
4 Partially correct 197 ms 24164 KB Output is partially correct
5 Partially correct 120 ms 16592 KB Output is partially correct
6 Partially correct 132 ms 18580 KB Output is partially correct
7 Partially correct 122 ms 17920 KB Output is partially correct
8 Partially correct 123 ms 19700 KB Output is partially correct
9 Partially correct 146 ms 17472 KB Output is partially correct
10 Partially correct 258 ms 26816 KB Output is partially correct
11 Partially correct 142 ms 20756 KB Output is partially correct
12 Partially correct 87 ms 13672 KB Output is partially correct
13 Partially correct 78 ms 12252 KB Output is partially correct
14 Partially correct 75 ms 11664 KB Output is partially correct
15 Partially correct 79 ms 10960 KB Output is partially correct
16 Partially correct 3 ms 596 KB Output is partially correct
17 Partially correct 70 ms 10564 KB Output is partially correct
18 Partially correct 72 ms 10556 KB Output is partially correct
19 Partially correct 70 ms 11324 KB Output is partially correct
20 Partially correct 107 ms 14372 KB Output is partially correct
21 Partially correct 111 ms 17688 KB Output is partially correct
22 Partially correct 86 ms 13336 KB Output is partially correct