oj.uz

Submission #422746

# Submission time Handle Problem Language Result Execution time Memory
422746 2021-06-10T11:38:45 Z alireza_kaviani Mechanical Doll (IOI18_doll) C++11
100 / 100
 133 ms 11892 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3e5 + 10;

int cnt , ans[MAXN];
vector<int> vec , C , X , Y;

int reverse(int x){
	int ans = 0;
	for(int i = 0 ; i < cnt ; i++){
		ans = ans * 2 + ((x & (1 << i)) != 0);
	}
	return ans;
}

int solve(int ql , int qr , int l , int r){
	if(r <= ql || qr <= l)	return -1;
	if(r - l == 1)	return ans[l];
	int id = X.size();
	X.push_back(-1); Y.push_back(-1);
	int mid = l + r >> 1; 
	int a = solve(ql , qr , l , mid);
	int b = solve(ql , qr , mid , r);
	X[id] = a; Y[id] = b;
	return -(id + 1);
}

void create_circuit(int M, vector<int> A) {
	fill(ans , ans + MAXN , -1);
	int k = 1 , n = A.size();
	while(k < n)	k *= 2 , cnt++;
	for(int i = k - n ; i < k ; i++){
		vec.push_back(reverse(i));
	}
	sort(vec.begin() , vec.end());
	C.push_back(A[0]);
	for(int i = 0 ; i < n ; i++){
		ans[reverse(vec[i])] = (i + 1 < n ? A[i + 1] : 0);
	}
	for(int i = 0 ; i < M ; i++)	C.push_back(-1);
/*	for(int i = 0 ; i < k ; i++){
		cout << ans[i] << endl;
	}
*/	solve(k - n , k , 0 , k);
/*	for(int i : C)	cout << i << ' ';
	cout << endl;
	for(int i : X)	cout << i << ' ';
	cout << endl;
	for(int i : Y)	cout << i << ' ';
	cout << endl;*/
	if(X.size() == 0)	X.push_back(-1);
	if(Y.size() == 0)	Y.push_back(0);
	answer(C , X , Y);
}

Compilation message

doll.cpp: In function 'int solve(int, int, int, int)':
doll.cpp:23:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 41 ms 5464 KB Output is correct
3 Correct 38 ms 5580 KB Output is correct
4 Correct 2 ms 1356 KB Output is correct
5 Correct 12 ms 2680 KB Output is correct
6 Correct 59 ms 6696 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 41 ms 5464 KB Output is correct
3 Correct 38 ms 5580 KB Output is correct
4 Correct 2 ms 1356 KB Output is correct
5 Correct 12 ms 2680 KB Output is correct
6 Correct 59 ms 6696 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 85 ms 8092 KB Output is correct
9 Correct 76 ms 9748 KB Output is correct
10 Correct 122 ms 11892 KB Output is correct
11 Correct 1 ms 1356 KB Output is correct
12 Correct 2 ms 1448 KB Output is correct
13 Correct 1 ms 1356 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 41 ms 5464 KB Output is correct
3 Correct 38 ms 5580 KB Output is correct
4 Correct 2 ms 1356 KB Output is correct
5 Correct 12 ms 2680 KB Output is correct
6 Correct 59 ms 6696 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 85 ms 8092 KB Output is correct
9 Correct 76 ms 9748 KB Output is correct
10 Correct 122 ms 11892 KB Output is correct
11 Correct 1 ms 1356 KB Output is correct
12 Correct 2 ms 1448 KB Output is correct
13 Correct 1 ms 1356 KB Output is correct
14 Correct 108 ms 11484 KB Output is correct
15 Correct 68 ms 9320 KB Output is correct
16 Correct 133 ms 11768 KB Output is correct
17 Correct 1 ms 1356 KB Output is correct
18 Correct 1 ms 1356 KB Output is correct
19 Correct 1 ms 1356 KB Output is correct
20 Correct 109 ms 11652 KB Output is correct
21 Correct 2 ms 1356 KB Output is correct
22 Correct 1 ms 1356 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 64 ms 6440 KB Output is correct
3 Correct 61 ms 6764 KB Output is correct
4 Correct 111 ms 8592 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 64 ms 6440 KB Output is correct
3 Correct 61 ms 6764 KB Output is correct
4 Correct 111 ms 8592 KB Output is correct
5 Correct 123 ms 10164 KB Output is correct
6 Correct 105 ms 9156 KB Output is correct
7 Correct 106 ms 9280 KB Output is correct
8 Correct 102 ms 9884 KB Output is correct
9 Correct 60 ms 6688 KB Output is correct
10 Correct 100 ms 8868 KB Output is correct
11 Correct 124 ms 8544 KB Output is correct
12 Correct 61 ms 7008 KB Output is correct
13 Correct 65 ms 6688 KB Output is correct
14 Correct 64 ms 7536 KB Output is correct
15 Correct 73 ms 7644 KB Output is correct
16 Correct 3 ms 1612 KB Output is correct
17 Correct 64 ms 6336 KB Output is correct
18 Correct 62 ms 6440 KB Output is correct
19 Correct 61 ms 7008 KB Output is correct
20 Correct 100 ms 9668 KB Output is correct
21 Correct 125 ms 8536 KB Output is correct
22 Correct 101 ms 8540 KB Output is correct