oj.uz

Submission #764662

# Submission time Handle Problem Language Result Execution time Memory
764662 2023-06-23T18:52:07 Z MetalPower Mechanical Doll (IOI18_doll) C++14
100 / 100
 200 ms 29924 KB 
#include "doll.h"

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

const int MX = 3e5 + 10;

int cnt[MX];
map<int, int> lf, rg;
vector<int> nx;

int _M, huge_mask = 0, tim = 0, mx_idx = 0;
vector<int> pos_starts;

int solve(int idx, int mask){
	if(idx > 0 && !(huge_mask >> (mx_idx - idx) & 1)){
		huge_mask ^= 1 << (mx_idx - idx);
		return -1;
	}else if(idx == mx_idx){
		pos_starts.push_back(mask);
		return 2 * _M + mask + 10;
	}else{
		++tim; int curr = -tim;
		lf[curr] = solve(idx + 1, mask);
		rg[curr] = solve(idx + 1, mask + (1 << idx));
		return curr;
	}
}

void create_circuit(int M, vector<int> A) {

	_M = M;
	int N = A.size();
	vector<int> C(M + 1), X, Y;

	if(N == 1){
		C[0] = A[0];
		for(int i = 1; i <= M; i++) C[i] = 0;
		answer(C, X, Y);
		return;
	}
	
	C[0] = A[0]; cnt[A[0]]++;
	for(int i = 1; i < N; i++) cnt[A[i]]++, nx.push_back(A[i]);
	nx.push_back(0);

	huge_mask = N - 1;
	for(int j = 0; j < 20; j++){
		if((1 << j) > huge_mask){
			mx_idx = j;
			break;
		}
	}

	for(int i = 1; i <= M; i++){
		if(cnt[i] == 0) C[i] = 0;
		else C[i] = -1;
	}

	solve(0, 0);
	sort(pos_starts.begin(), pos_starts.end());

	for(int i = -1; i >= -tim; i--){
		if(lf[i] > M){
			int curr_mask = lf[i] - 2 * M - 10;
			int idx = lower_bound(pos_starts.begin(), pos_starts.end(), curr_mask) - pos_starts.begin();
			X.push_back(nx[idx]);
		}else{
			X.push_back(lf[i]);
		}
		if(rg[i] > M){
			int curr_mask = rg[i] - 2 * M - 10;
			int idx = lower_bound(pos_starts.begin(), pos_starts.end(), curr_mask) - pos_starts.begin();
			Y.push_back(nx[idx]);
		}else{
			Y.push_back(rg[i]);
		}
	}

	answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 58 ms 11068 KB Output is correct
3 Correct 59 ms 10772 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 97 ms 16068 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 58 ms 11068 KB Output is correct
3 Correct 59 ms 10772 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 97 ms 16068 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 119 ms 19632 KB Output is correct
9 Correct 129 ms 20436 KB Output is correct
10 Correct 200 ms 29924 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 58 ms 11068 KB Output is correct
3 Correct 59 ms 10772 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 97 ms 16068 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 119 ms 19632 KB Output is correct
9 Correct 129 ms 20436 KB Output is correct
10 Correct 200 ms 29924 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 189 ms 29336 KB Output is correct
15 Correct 130 ms 19696 KB Output is correct
16 Correct 188 ms 29160 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 192 ms 29624 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

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 304 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 212 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 109 ms 18944 KB Output is correct
3 Correct 119 ms 19156 KB Output is correct
4 Correct 190 ms 28500 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 109 ms 18944 KB Output is correct
3 Correct 119 ms 19156 KB Output is correct
4 Correct 190 ms 28500 KB Output is correct
5 Correct 196 ms 29060 KB Output is correct
6 Correct 189 ms 28648 KB Output is correct
7 Correct 188 ms 28752 KB Output is correct
8 Correct 182 ms 28580 KB Output is correct
9 Correct 116 ms 19200 KB Output is correct
10 Correct 190 ms 28524 KB Output is correct
11 Correct 175 ms 28396 KB Output is correct
12 Correct 116 ms 19136 KB Output is correct
13 Correct 112 ms 19032 KB Output is correct
14 Correct 119 ms 19512 KB Output is correct
15 Correct 118 ms 19600 KB Output is correct
16 Correct 4 ms 852 KB Output is correct
17 Correct 114 ms 18960 KB Output is correct
18 Correct 109 ms 18948 KB Output is correct
19 Correct 119 ms 19196 KB Output is correct
20 Correct 190 ms 28456 KB Output is correct
21 Correct 187 ms 28520 KB Output is correct
22 Correct 182 ms 28500 KB Output is correct