oj.uz

Submission #1026099

# Submission time Handle Problem Language Result Execution time Memory
1026099 2024-07-17T14:51:32 Z Lalic Mechanical Doll (IOI18_doll) C++17
69.553 / 100
 82 ms 10716 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

int cnt, m;

void add(int ver, int root, int depth, int& tot, vector<int>& X, vector<int>& Y, vector<int>& state){
	if(!tot){
		if(Y[ver-m-1]==-1) Y[ver-m-1]=root;
		if(X[ver-m-1]==-1) X[ver-m-1]=root;
		return;
	}
	
	if(!depth){
		tot--;
		if(!tot) X[ver-m-1]=root;
		else tot--;
		return;
	}
	
	Y[ver-m-1]=++cnt;
	X.pb(-1); Y.pb(-1);
	state.pb(0);
	add(cnt, root, depth-1, tot, X, Y, state);
	
	if(!tot) X[ver-m-1]=root;
	else{
		X[ver-m-1]=++cnt;
		X.pb(-1); Y.pb(-1);
		state.pb(0);
		add(cnt, root, depth-1, tot, X, Y, state);
	}
}

void calc(int p, int qnt, vector<int>& C, vector<int>& X, vector<int>& Y, vector<int>& state){
	if(qnt==1) return;
	
	int cam=0;
	
	while((1<<cam)<qnt) cam++;
	
	C[p]=++cnt;
	X.pb(-1); Y.pb(-1);
	state.pb(0);
	
	add(cnt, cnt, cam-1, qnt, X, Y, state);
}

void create_circuit(int M, vector<int> A) {
	cnt=M;
	m=M;
	
	A.pb(0);
	vector<int> C(M+1, -1), X, Y, freq(M+1, 0), state;
	for(auto u : A) freq[u]++;
	
	int curr=0;
	for(auto u : A){
		if(C[curr]==-1) calc(curr, freq[curr], C, X, Y, state);
		
		if(C[curr]==-1){
			//~ cout << "curr = " << curr << "\n";
			C[curr]=u;
			curr=u;
			continue;
		}
		
		curr=C[curr];
		//~ cout << "curr = " << curr << "\n";
		while(1){
			if(!state[curr-m-1]){
				state[curr-m-1]=1-state[curr-m-1];
				
				if(X[curr-m-1]==-1){
					X[curr-m-1]=u;
					break;
				}
				else curr=X[curr-m-1];
				
				//~ cout << "curr = " << curr << "\n";
			}
			else{
				state[curr-m-1]=1-state[curr-m-1];
				
				if(Y[curr-m-1]==-1){
					Y[curr-m-1]=u;
					break;
				}
				else curr=Y[curr-m-1];
				
				//~ cout << "curr = " << curr << "\n";
			}
		}
		
		curr=u;
	}
	
	for(auto& u : C)
		if(u>m) u=m-u;
	for(auto& u : X)
		if(u>m) u=m-u;
	for(auto& u : Y)
		if(u>m) u=m-u;
	
	answer(C, X, Y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 11 ms 2904 KB wrong serial number
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 11 ms 2904 KB wrong serial number
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 11 ms 2904 KB wrong serial number
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 46 ms 6996 KB Output is correct
3 Correct 57 ms 5868 KB Output is correct
4 Correct 82 ms 9388 KB Output is correct

Subtask #6
41.5530038336 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 46 ms 6996 KB Output is correct
3 Correct 57 ms 5868 KB Output is correct
4 Correct 82 ms 9388 KB Output is correct
5 Partially correct 76 ms 10716 KB Output is partially correct
6 Partially correct 51 ms 10564 KB Output is partially correct
7 Partially correct 53 ms 10564 KB Output is partially correct
8 Partially correct 50 ms 10052 KB Output is partially correct
9 Partially correct 54 ms 5840 KB Output is partially correct
10 Partially correct 77 ms 9796 KB Output is partially correct
11 Partially correct 62 ms 9448 KB Output is partially correct
12 Partially correct 40 ms 6192 KB Output is partially correct
13 Partially correct 35 ms 6944 KB Output is partially correct
14 Partially correct 35 ms 7120 KB Output is partially correct
15 Partially correct 34 ms 6960 KB Output is partially correct
16 Partially correct 1 ms 604 KB Output is partially correct
17 Partially correct 35 ms 6188 KB Output is partially correct
18 Partially correct 38 ms 5840 KB Output is partially correct
19 Partially correct 38 ms 6104 KB Output is partially correct
20 Partially correct 51 ms 9540 KB Output is partially correct
21 Partially correct 58 ms 9284 KB Output is partially correct
22 Partially correct 52 ms 9256 KB Output is partially correct