oj.uz

Submission #779475

# Submission time Handle Problem Language Result Execution time Memory
779475 2023-07-11T13:09:35 Z amunduzbaev Mechanical Doll (IOI18_doll) C++17
84 / 100
 125 ms 13656 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

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];
	}
	
	answer(c, x, y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 53 ms 6612 KB Output is correct
3 Correct 47 ms 6204 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 71 ms 7888 KB Output is correct
7 Incorrect 0 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 0 ms 212 KB Output is correct
2 Correct 53 ms 6612 KB Output is correct
3 Correct 47 ms 6204 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 71 ms 7888 KB Output is correct
7 Incorrect 0 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 0 ms 212 KB Output is correct
2 Correct 53 ms 6612 KB Output is correct
3 Correct 47 ms 6204 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 71 ms 7888 KB Output is correct
7 Incorrect 0 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 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 89 ms 10572 KB Output is correct
3 Correct 90 ms 10564 KB Output is correct
4 Correct 118 ms 13228 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 89 ms 10572 KB Output is correct
3 Correct 90 ms 10564 KB Output is correct
4 Correct 118 ms 13228 KB Output is correct
5 Correct 121 ms 13656 KB Output is correct
6 Correct 122 ms 13404 KB Output is correct
7 Correct 120 ms 13488 KB Output is correct
8 Correct 114 ms 13360 KB Output is correct
9 Correct 90 ms 10564 KB Output is correct
10 Correct 114 ms 13300 KB Output is correct
11 Correct 113 ms 13244 KB Output is correct
12 Correct 95 ms 10576 KB Output is correct
13 Correct 110 ms 10700 KB Output is correct
14 Correct 91 ms 10696 KB Output is correct
15 Correct 97 ms 10820 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 98 ms 11072 KB Output is correct
18 Correct 89 ms 10560 KB Output is correct
19 Correct 91 ms 10580 KB Output is correct
20 Correct 112 ms 13304 KB Output is correct
21 Correct 125 ms 13372 KB Output is correct
22 Correct 113 ms 13172 KB Output is correct