oj.uz

Submission #416679

# Submission time Handle Problem Language Result Execution time Memory
416679 2021-06-02T18:27:22 Z sofapuden Mechanical Doll (IOI18_doll) C++14
100 / 100
 124 ms 12644 KB 
#include "doll.h"
#include<bits/stdc++.h>
 
using namespace std;
 
vector<int> X, Y, A, FLG;
int h, v, n;

const int UNDEF = 7e6+5;

int cn = 0;
int cnt = 0;

void fin(int x, int p, int am, int val, bool ok){
	//cout << "x: " << x << " p: " << p << " am: " << am << " val: " << val << " ok: " << ok << endl;
	if(!am){
		//cout << "Hey" << endl;
		cnt--;
		if(ok){
			Y[p] = -1;
		}
		else X[p] = -1;
		fin(0,0,n,v,0);
		return;
	}
	if(!val){
		//cout << "HeY" << endl;
		cnt--;
		if(ok){
			Y[p] = A[cn++];
		}
		else X[p] = A[cn++];
		if(cn == n)return;
		fin(0,0,n,v,0);
		return;
	}
	if((int)X.size() <= x){
		X.push_back(UNDEF);
		Y.push_back(UNDEF);
		FLG.push_back(0);
		X.back() = -(++cnt)-1;
		fin(cnt,x,max(0,am-val),val>>1,0);
		return;
	}
	FLG[x]^=1;
	if(FLG[x]){
		if(Y[x] == UNDEF){
			Y[x] = -(++cnt)-1;
			fin(cnt,x,min(am,val),val>>1,1);
		}
		else if(Y[x] == -1){
			fin(0,0,n,v,0);
		}
		else{
			fin(-Y[x]-1,x,min(am,val),val>>1,1);
		}
	}
	else if(X[x] == -1){
		fin(0,0,n,v,0);
	}
	else{
		fin(-X[x]-1,x,max(0,am-val),val>>1,0);
	}
}
 
void create_circuit(int m, vector<int> _A) {
	_A.push_back(0);
	n = _A.size();
	A = _A;
	vector<int> C(m+1,-1);
	h = ceil(log2(n));
	v = (1<<(h-1)); 
	fin(0,0,n,v,0);

	//for(int i : C)cout << i << ' ';cout << endl;
	//for(int i : X)cout << i << ' ';cout << endl;
	//for(int i : Y)cout << i << ' ';cout << endl;

	answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 49 ms 4524 KB Output is correct
3 Correct 44 ms 4748 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 60 ms 7496 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 49 ms 4524 KB Output is correct
3 Correct 44 ms 4748 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 60 ms 7496 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 76 ms 8244 KB Output is correct
9 Correct 79 ms 8804 KB Output is correct
10 Correct 113 ms 12644 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 49 ms 4524 KB Output is correct
3 Correct 44 ms 4748 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1484 KB Output is correct
6 Correct 60 ms 7496 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 76 ms 8244 KB Output is correct
9 Correct 79 ms 8804 KB Output is correct
10 Correct 113 ms 12644 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 110 ms 12148 KB Output is correct
15 Correct 77 ms 7972 KB Output is correct
16 Correct 107 ms 11896 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 115 ms 12516 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 292 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 71 ms 6232 KB Output is correct
3 Correct 69 ms 6208 KB Output is correct
4 Correct 102 ms 9760 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 71 ms 6232 KB Output is correct
3 Correct 69 ms 6208 KB Output is correct
4 Correct 102 ms 9760 KB Output is correct
5 Correct 124 ms 11024 KB Output is correct
6 Correct 107 ms 10636 KB Output is correct
7 Correct 104 ms 10760 KB Output is correct
8 Correct 103 ms 10532 KB Output is correct
9 Correct 68 ms 6172 KB Output is correct
10 Correct 103 ms 10404 KB Output is correct
11 Correct 103 ms 10156 KB Output is correct
12 Correct 70 ms 6456 KB Output is correct
13 Correct 77 ms 6820 KB Output is correct
14 Correct 71 ms 6924 KB Output is correct
15 Correct 75 ms 7072 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 64 ms 6968 KB Output is correct
18 Correct 70 ms 6440 KB Output is correct
19 Correct 73 ms 6456 KB Output is correct
20 Correct 102 ms 10388 KB Output is correct
21 Correct 107 ms 10136 KB Output is correct
22 Correct 101 ms 10192 KB Output is correct