oj.uz

Submission #1042234

# Submission time Handle Problem Language Result Execution time Memory
1042234 2024-08-02T17:16:51 Z amunduzbaev Mechanical Doll (IOI18_doll) C++17
10 / 100
 106 ms 13008 KB 
#include "doll.h"

#include "bits/stdc++.h"
using namespace std;

void create_circuit(int m, vector<int> a) {
	vector<int> c(m + 1, -1);
	//~ for(auto x : a){
		//~ cout<<x<<" ";
	//~ } cout<<endl;
	
	c[0] = a[0];
	a.erase(a.begin());
	//~ a.push_back(0);
	
	//~ for(auto x : a){
		//~ cout<<x<<" ";
	//~ } cout<<endl;
	
	//~ cout<<"Been here: 1"<<endl;
	
	int n = a.size() + 1;
	int x_ = __lg(n);
	
	if((1 << x_) < n) x_++;
	
	vector<int> x, y;
	int last = 0;
	
	auto get = [&](){
		x.push_back(0);
		y.push_back(0);
		last++;
		
		return last;
	};
	
	//~ cout<<"Been here: 2"<<endl;
	
	function<int(int, int, vector<int>)> buildTree = [&](int l, int r, vector<int> a){
		//~ cout<<l<<" "<<r<<" : ";
		//~ for(auto x : a) cout<<x<<" ";
		//~ cout<<endl;
		
		if((int)a.size() == 0){
			if(r == (1 << x_) - 1){
				if(l == r) return 0;
				
				int m = (l + r) >> 1;
				int root = get();
				
				x[root - 1] = -1;
				y[root - 1] = buildTree(m + 1, r, a);
				
				//~ cout<<"vertex: "<<-root<<" "<<x[root - 1]<<" "<<y[root - 1]<<endl;
				
				return -root;
			}
			
			return -1;
		}
		if(l == r){
			assert((int)a.size() == 1);
			return a[0];
		}
		
		int m = (l + r) >> 1;
		int l_sz = m - l + 1;
		// [l, m], [m + 1, r]
		
		int goRight = (int)a.size() - l_sz;
		vector<int> goL, goR;
		
		for(int i=0;i<(int)a.size();i++){
			if(i % 2 == 0 || (int)goR.size() == goRight){
				goL.push_back(a[i]);
			} else {
				goR.push_back(a[i]);
			}
		}
		
		int root = get();
		
		//~ int LeftRoot = buildTree(l, m, goL);
		//~ int RightRoot = buildTree(m + 1, r, goR);
		
		//~ cout<<"before: " <<LeftRoot<<" "<<RightRoot<<endl;
		
		x[root - 1] = buildTree(l, m, goL);
		y[root - 1] = buildTree(m + 1, r, goR);
		
		//~ x[root - 1] = LeftRoot;
		//~ y[root - 1] = RightRoot;
		
		//~ cout<<"vertex: "<<-root<<" "<<x[root - 1]<<" "<<y[root - 1]<<endl;
		
		return -root;
		//~ buildTree(l, m, goL);
		//~ buildTree(m + 1, r, goR);
	};
	
	buildTree(0, (1 << x_) - 1, a);
	
	vector<int> dir(last, 0);
	
	function<int(int, int)> simulate = [&](int root, int value){
		//~ cout<<root<<" "<<value<<endl;
		if(root >= 0){
			return value;
		}
		
		root = -root;
		
		dir[root - 1] ^= 1;
		if(dir[root - 1] != 0){
			x[root - 1] = simulate(x[root - 1], value);
		} else {
			y[root - 1] = simulate(y[root - 1], value);
		}
		
		return -root;
	};
	
	for(int i=0;i<(int)a.size();i++){
		simulate(-1, a[i]);
	}
	
	//~ for(int i=0;i<(int)a.size();i++){
		//~ cout<<a[i]<<" ";
	//~ } cout<<"\n";
	
	//~ for(int i=0;i<=m;i++){
		//~ cout<<c[i]<<" ";
	//~ } cout<<endl;
	
	//~ for(int i=0;i<last;i++){
		//~ cout<<x[i]<<" ";
	//~ } cout<<endl;
	
	//~ for(int i=0;i<last;i++){
		//~ cout<<y[i]<<" ";
	//~ } cout<<endl;
	
	assert(last <= n + x_ * 2);
	
	answer(c, x, y);
	
	return;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 35 ms 4516 KB Output is correct
3 Correct 36 ms 4532 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Runtime error 52 ms 7668 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 35 ms 4516 KB Output is correct
3 Correct 36 ms 4532 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Runtime error 52 ms 7668 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 35 ms 4516 KB Output is correct
3 Correct 36 ms 4532 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Runtime error 52 ms 7668 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 65 ms 6328 KB Output is correct
3 Correct 70 ms 7100 KB Output is correct
4 Runtime error 106 ms 13008 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 65 ms 6328 KB Output is correct
3 Correct 70 ms 7100 KB Output is correct
4 Runtime error 106 ms 13008 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -