oj.uz

Submission #782532

# Submission time Handle Problem Language Result Execution time Memory
782532 2023-07-14T04:25:01 Z boyliguanhan Mechanical Doll (IOI18_doll) C++17
100 / 100
 102 ms 11692 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> X, Y;
int N, s_state[200100];
 
int CALCTREE(int l, int r) {
	if(l >= N) return -1;
	if(r - 1 > l) {
		int mid = l+r>>1;
        X.push_back(0), Y.push_back(0);
        int pos = X.size()-1;
		Y[pos]=(CALCTREE(l, mid));
		X[pos]=(CALCTREE(mid, r));
		return -pos-1;
	}
	return 1;
}
 
void create_circuit(int M, vector<int> A) {
	vector<int> C(M+1,-1);
	A.push_back(0);
	N = A.size();
    int x = 1;
	while(x<N)
        x *= 2;
	CALCTREE(0, x);
	for(int &i : A) {
		int cur_switch = 0;
		while(cur_switch >= 0) {
			s_state[cur_switch] ^= 1;
			int &w = s_state[cur_switch] ? X[cur_switch] : Y[cur_switch];
			if(w >= 0)
                w = i, cur_switch = -1;
			else
                cur_switch = -1-w;
		}
	}
	answer(C, X, Y);
}

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 33 ms 4552 KB Output is correct
3 Correct 29 ms 4572 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 45 ms 6628 KB Output is correct
7 Correct 0 ms 312 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 33 ms 4552 KB Output is correct
3 Correct 29 ms 4572 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 45 ms 6628 KB Output is correct
7 Correct 0 ms 312 KB Output is correct
8 Correct 61 ms 7664 KB Output is correct
9 Correct 74 ms 8044 KB Output is correct
10 Correct 94 ms 11692 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 304 KB Output is correct
13 Correct 1 ms 316 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 33 ms 4552 KB Output is correct
3 Correct 29 ms 4572 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 45 ms 6628 KB Output is correct
7 Correct 0 ms 312 KB Output is correct
8 Correct 61 ms 7664 KB Output is correct
9 Correct 74 ms 8044 KB Output is correct
10 Correct 94 ms 11692 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 304 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 101 ms 11392 KB Output is correct
15 Correct 63 ms 7268 KB Output is correct
16 Correct 90 ms 11208 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 93 ms 11508 KB Output is correct
21 Correct 1 ms 312 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 212 KB Output is correct
3 Correct 0 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 54 ms 6436 KB Output is correct
3 Correct 56 ms 6528 KB Output is correct
4 Correct 83 ms 9884 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 54 ms 6436 KB Output is correct
3 Correct 56 ms 6528 KB Output is correct
4 Correct 83 ms 9884 KB Output is correct
5 Correct 89 ms 11096 KB Output is correct
6 Correct 89 ms 10936 KB Output is correct
7 Correct 96 ms 11068 KB Output is correct
8 Correct 88 ms 10640 KB Output is correct
9 Correct 55 ms 6512 KB Output is correct
10 Correct 89 ms 10608 KB Output is correct
11 Correct 87 ms 10236 KB Output is correct
12 Correct 57 ms 6760 KB Output is correct
13 Correct 63 ms 7196 KB Output is correct
14 Correct 58 ms 7228 KB Output is correct
15 Correct 62 ms 7324 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 57 ms 7040 KB Output is correct
18 Correct 70 ms 6756 KB Output is correct
19 Correct 57 ms 6780 KB Output is correct
20 Correct 89 ms 10468 KB Output is correct
21 Correct 86 ms 10256 KB Output is correct
22 Correct 102 ms 10244 KB Output is correct