oj.uz

Submission #1041562

# Submission time Handle Problem Language Result Execution time Memory
1041562 2024-08-02T05:50:05 Z amunduzbaev Mechanical Doll (IOI18_doll) C++17
0 / 100
 23 ms 9048 KB 
#include "doll.h"

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

#define ar array
typedef long long ll;

template<class T> bool umin(T& a, const T b){ if(a > b) { a = b; return true; } return false; }
template<class T> bool umax(T& a, const T b){ if(a < b) { a = b; return true; } return false; }

void create_circuit(int m, vector<int> a) {
	int n = a.size();
	
	vector<int> c(m + 1), x_(m), y_(m);
	vector<int> cnt(m + 1);
	
	a.insert(a.begin(), 0);
	a.push_back(0);
	
	for(int i=0;i<=n;i++){
		cnt[a[i]]++;
	}
	
	vector<vector<int>> out(m + 1);
	for(int i=1;i<=n+1;i++){
		int x = a[i - 1], y = a[i];
		
		//~ out[x].push_back(y);
		
		if(cnt[y] == 1){
			out[x].push_back(y);
		}  else {
			out[x].push_back(-y);
		}
	}
	
	int last = m;
	
	auto get = [&](){
		x_.push_back(0);
		y_.push_back(0);
		
		return ++last;
	};
	
	function<int(vector<int>&, int)> dfs = [&](vector<int>& a, int v){
		if((int)a.size() == 1){
			return a[0];
		}
		
		vector<int> l, r;
		for(int i=0;i<(int)a.size();i++){
			if(i & 1) r.push_back(a[i]);
			else l.push_back(a[i]);
		}
		
		if(v == 0){
			v = get();
		}
		
		if((int)a.size() & 1){
			r.push_back(l.back());
			l.back() = -v;
		}
		
		//~ cout<<"before: "<<dfs(l, 0)<<" "<<dfs(r, 0)<<endl;
		int tmpLeft = dfs(l, 0);
		int tmpRight = dfs(r, 0);
		x_[v - 1] = tmpLeft;
		y_[v - 1] = tmpRight;
		
		return -v;
	};
	
	//~ for(int i=0;i<=m;i++){
		//~ cout<<cnt[i]<<" ";
	//~ } cout<<endl;
	
	for(int i=0;i<=m;i++){
		if(!cnt[i]) continue;
		if(cnt[i] == 1){
			//~ cout<<i<<endl;
			c[i] = out[i][0];
			continue;
		}
		
		vector<int> a_(cnt[i], i);
		
		//~ cout<<i<<" : ";
		//~ for(auto x : a_) cout<<x<<" ";
		//~ cout<<endl;
		
		dfs(a_, i);
		//~ x_[i - 1] = x_[root];
		//~ y_[i - 1] = y_[root];
		
		c[i] = dfs(out[i], 0);
	}
		
	//~ for(int i=0;i<=m;i++){
		//~ cout<<i<<" : ";
		//~ for(auto x : out[i]) cout<<x<<" ";
		//~ cout<<endl;
	//~ }
	
	//~ for(int i=0;i<=m;i++){
		//~ cout<<i<<" "<<c[i]<<"\n";
		//~ cout<<c[i]<<" ";
	//~ }
	//~ cout<<endl;
	
	//~ cout<<(int)x_.size()<<" "<<last<<endl;
	//~ for(int i=0;i<last;i++){
		//~ cout<<-(i + 1)<<" ";
	//~ } cout<<endl;
	
	//~ for(int i=0;i<last;i++){
		//~ if(!x_[i]) continue;
		//~ cout<<-(i + 1)<<" "<<x_[i]<<"\n";
		//~ cout<<x_[i]<<" ";
	//~ } cout<<endl;
	
	//~ for(int i=0;i<last;i++){
		//~ if(!y_[i]) continue;
		//~ cout<<-(i + 1)<<" "<<y_[i]<<"\n";
		//~ cout<<y_[i]<<" ";
	//~ } cout<<endl;
	
	answer(c, x_, y_);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 23 ms 9048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 23 ms 9048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 23 ms 9048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0.0 / 18.0

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

Subtask #6
0.0 / 56.0

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