oj.uz

Submission #713764

# Submission time Handle Problem Language Result Execution time Memory
713764 2023-03-23T02:52:58 Z Foxyy Mechanical Doll (IOI18_doll) C++17
6 / 100
 83 ms 11592 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);
	
//	assert(mp.size() == vec.size());
	int i = 0;
	for (auto [f, s] : mp) {
		auto [switch_id, exit_id] = s;
		if (exit_id == 0) {
			get_switch(switch_id).x = vec[i++];
		} else {
			get_switch(switch_id).y = vec[i++];
		}
	}
}

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 {
			C[i] = create_switch_tree((int)vec[i].size()-1);
//			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 0 ms 212 KB Output is correct
2 Correct 22 ms 6300 KB Output is correct
3 Correct 20 ms 5144 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 10 ms 3744 KB Output is correct
6 Correct 47 ms 7700 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 0 ms 212 KB Output is correct
2 Correct 22 ms 6300 KB Output is correct
3 Correct 20 ms 5144 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 10 ms 3744 KB Output is correct
6 Correct 47 ms 7700 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 44 ms 7740 KB Output is correct
9 Correct 44 ms 8904 KB Output is correct
10 Correct 79 ms 11592 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 22 ms 6300 KB Output is correct
3 Correct 20 ms 5144 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 10 ms 3744 KB Output is correct
6 Correct 47 ms 7700 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 44 ms 7740 KB Output is correct
9 Correct 44 ms 8904 KB Output is correct
10 Correct 79 ms 11592 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Incorrect 83 ms 10416 KB state 'Y'
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB state 'Y'
2 Halted 0 ms 0 KB -