oj.uz

Submission #779504

# Submission time Handle Problem Language Result Execution time Memory
779504 2023-07-11T13:32:06 Z amunduzbaev Mechanical Doll (IOI18_doll) C++17
84 / 100
 122 ms 13676 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 <= n - 1 + __lg(2 * (n - 1) - 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 212 KB Output is correct
2 Correct 49 ms 6592 KB Output is correct
3 Correct 50 ms 6092 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 61 ms 7896 KB Output is correct
7 Runtime error 1 ms 340 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 49 ms 6592 KB Output is correct
3 Correct 50 ms 6092 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 61 ms 7896 KB Output is correct
7 Runtime error 1 ms 340 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 49 ms 6592 KB Output is correct
3 Correct 50 ms 6092 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 61 ms 7896 KB Output is correct
7 Runtime error 1 ms 340 KB Execution killed with signal 6
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 0 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 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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 87 ms 10456 KB Output is correct
3 Correct 89 ms 10492 KB Output is correct
4 Correct 111 ms 13156 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 87 ms 10456 KB Output is correct
3 Correct 89 ms 10492 KB Output is correct
4 Correct 111 ms 13156 KB Output is correct
5 Correct 122 ms 13676 KB Output is correct
6 Correct 115 ms 13532 KB Output is correct
7 Correct 117 ms 13500 KB Output is correct
8 Correct 122 ms 13404 KB Output is correct
9 Correct 86 ms 10548 KB Output is correct
10 Correct 113 ms 13276 KB Output is correct
11 Correct 111 ms 13164 KB Output is correct
12 Correct 87 ms 10452 KB Output is correct
13 Correct 89 ms 10696 KB Output is correct
14 Correct 89 ms 10696 KB Output is correct
15 Correct 90 ms 10820 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 87 ms 11072 KB Output is correct
18 Correct 88 ms 10560 KB Output is correct
19 Correct 87 ms 10576 KB Output is correct
20 Correct 113 ms 13272 KB Output is correct
21 Correct 112 ms 13144 KB Output is correct
22 Correct 113 ms 13168 KB Output is correct