oj.uz

Submission #779481

# Submission time Handle Problem Language Result Execution time Memory
779481 2023-07-11T13:19:13 Z amunduzbaev Mechanical Doll (IOI18_doll) C++17
84 / 100
 184 ms 15464 KB 
#include "doll.h"
#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef int64_t ll;
typedef int32_t ii;
//~ #define int ll

bool check(vector<int> c, vector<int> x, vector<int> y, vector<int> b){
	int u = 0, sz = x.size();
	vector<int> sw(sz), a;
	
	do{
		if(u > 0){
			a.push_back(u);
		}
		if(u >= 0){
			u = c[u];
			continue;
		}
		
		int p = u;
		if(!sw[-u - 1]){
			u = x[-u - 1];
		} else {
			u = y[-u - 1];
		}
		
		sw[-p - 1] ^= 1;
	}while(u);
	
	//~ for(auto x : a) cout<<x<<" ";
	//~ cout<<"\n";
	//~ for(auto x : b) cout<<x<<" ";
	//~ cout<<"\n";
	
	for(int i=0;i<sz;i++){
		if(sw[i]) return false;
	}
	
	if(a != b) return false;
	
	return true;
};

void create_circuit(ii m, vector<ii> a){
	a.push_back(0);
	int n = a.size(); 
	
	int sz = 1;
	while(sz <= n) sz <<= 1;
	vector<int> used(sz * 2);
	function<void(int, int, int)> dfs = [&](int lx, int rx, int x){
		if(rx + n <= sz){
			return;
		}
		used[x] = 1;
		if(lx == rx){
			return;
		}
		
		int m = (lx + rx) >> 1;
		dfs(lx, m, x << 1);
		dfs(m + 1, rx, x << 1 | 1);
	};
	
	dfs(1, sz, 1);
	
	vector<int> sw(sz * 2), pos(sz);
	for(int i=0;i<sz;i++){
		function<void(int, int, int)> go = [&](int x, int lx, int rx){
			if(lx == rx){
				pos[lx] = i;
				return;
			}
			
			int m = (lx + rx) >> 1;
			if(sw[x]) go(x << 1 | 1, m + 1, rx);
			else go(x << 1, lx, m);
			
			sw[x] ^= 1;
		};
		
		go(1, 0, sz - 1);
	}
	
	int last = 0;
	vector<int> id;
	for(int i=0;i<sz;i++){
		if(used[i]){
			used[i] = -(++last);
			id.push_back(i);
		} else {
			used[i] = -1;
		}
	}
	
	fill(used.begin() + sz, used.end(), -1);
	vector<int> p(n); 
	iota(p.begin(), p.end(), sz - n);
	sort(p.begin(), p.end(), [&](int i, int j){
		return pos[i] < pos[j];
	});
	
	for(int i=0;i<n;i++){
		used[sz + p[i]] = a[i];
	}
	
	//~ assert(last <= n - 1 + __lg(n - 1));
	//~ assert(last <= 2 * (n - 1));
	
	vector<int> c(m + 1, -1), x(last), y(last);
	for(int i=0;i<last;i++){
		x[i] = used[id[i] << 1];
		y[i] = used[id[i] << 1 | 1];
	}
	
	a.pop_back();
	assert(check(c, x, y, a));
	
	answer(c, x, y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 69 ms 6844 KB Output is correct
3 Correct 63 ms 6732 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1444 KB Output is correct
6 Correct 84 ms 8524 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 69 ms 6844 KB Output is correct
3 Correct 63 ms 6732 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1444 KB Output is correct
6 Correct 84 ms 8524 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 69 ms 6844 KB Output is correct
3 Correct 63 ms 6732 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1444 KB Output is correct
6 Correct 84 ms 8524 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 119 ms 11708 KB Output is correct
3 Correct 127 ms 12228 KB Output is correct
4 Correct 160 ms 15192 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 119 ms 11708 KB Output is correct
3 Correct 127 ms 12228 KB Output is correct
4 Correct 160 ms 15192 KB Output is correct
5 Correct 173 ms 15464 KB Output is correct
6 Correct 184 ms 15360 KB Output is correct
7 Correct 170 ms 15384 KB Output is correct
8 Correct 162 ms 15296 KB Output is correct
9 Correct 117 ms 12228 KB Output is correct
10 Correct 160 ms 15264 KB Output is correct
11 Correct 159 ms 15084 KB Output is correct
12 Correct 123 ms 12120 KB Output is correct
13 Correct 128 ms 11784 KB Output is correct
14 Correct 122 ms 12360 KB Output is correct
15 Correct 125 ms 12356 KB Output is correct
16 Correct 4 ms 724 KB Output is correct
17 Correct 119 ms 11848 KB Output is correct
18 Correct 158 ms 11740 KB Output is correct
19 Correct 132 ms 12228 KB Output is correct
20 Correct 166 ms 15164 KB Output is correct
21 Correct 167 ms 15200 KB Output is correct
22 Correct 170 ms 15164 KB Output is correct