oj.uz

Submission #442856

# Submission time Handle Problem Language Result Execution time Memory
442856 2021-07-09T09:26:13 Z vanic Mechanical Doll (IOI18_doll) C++14
100 / 100
 108 ms 13104 KB 
#include "doll.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
 
using namespace std;
 
const int maxn=1e5+5, Log=17, pot=(1<<Log), inf=1e9;
 
vector < int > vez;
vector < int > x, y;
int m, n;
vector < int > red;
 
void napravi(int bit){
	int br=0;
	for(int i=0; i<(1<<bit); i++){
		red.push_back(br);
		for(int j=bit-1; j>-1; j--){
			if((1<<j)&br){
				br-=(1<<j);
			}
			else{
				br+=(1<<j);
				break;
			}
		}
	}
/*	for(int i=0; i<red.size(); i++){
		cout << red[i] << ' ';
	}
	cout << endl;*/
}
 
int bit;
int poz;
int mini;
int tren;
 
struct Logaritamska{
	vector < int > l;
	int siz;
	void precompute(int sz){
		siz=sz;
		l.clear();
		while(sz--){
			l.push_back(0);
		}
	}
	void update(int x, int val){
		for(; x<siz; x+=(x & -x)){
			l[x]+=val;
		}
	}
	int query(int x){
		int sol=0;
		for(; x>0; x-=(x & -x)){
			sol+=l[x];
		}
		return sol;
	}
};
 
 
Logaritamska L;
 
 
vector < int > A;
 
int siri(int cor, int val, int dep, int pos){
	if(bit==dep){
//		cout << red[cor] << endl;
		if(L.query(red[cor]+1)==L.query(red[cor])){
			int ind=red[cor]-L.query(red[cor]);
			return A[ind];
		}
		else{
			return inf;
		}
	}
	int a, b;
	x.push_back(0);
	y.push_back(0);
	mini=min(mini, val);
	a=siri(cor, val-1, dep+1, pos);
	b=siri(cor+(1<<(bit-dep-1)), mini-1, dep+1, pos);
	if(a==inf && b==inf){
		x.pop_back();
		y.pop_back();
		if(mini==val){
			mini++;
		}
		return inf;
	}
	if(b==inf){
		b=pos;
	}
	else if(a==inf){
		a=pos;
	}
	x[-1-val]=a;
	y[-1-val]=b;
	return val;
}
 

void rijesi(){
	int br;
	int raz;
	br=1;
	bit=0;
	for(int i=0; i<m+1; i++){
		vez.push_back(-1);
	}
	while((int)A.size()>br){
		br*=2;
		bit++;
	}
	red.clear();
	napravi(bit);
	L.precompute(br+5);
	raz=br-A.size();
	for(int j=0; j<raz; j++){
		L.update(red[j]+1, 1);
	}
	siri(0, -1, 0, -1);
}
 
void create_circuit(int M, vector <int> a){
	m=M;
	n=a.size();
	a.push_back(0);
	A=a;
	rijesi();
/*	for(int i=0; i<(int)vez.size(); i++){
		cout << vez[i] << ' ';
	}
	cout << endl;
	for(int i=0; i<(int)x.size(); i++){
		cout << x[i] << ' ' << y[i] << endl;
	}*/
	answer(vez, 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 45 ms 5952 KB Output is correct
3 Correct 41 ms 5516 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 58 ms 7756 KB Output is correct
7 Correct 0 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 45 ms 5952 KB Output is correct
3 Correct 41 ms 5516 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 58 ms 7756 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 76 ms 9652 KB Output is correct
9 Correct 91 ms 10040 KB Output is correct
10 Correct 103 ms 13104 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 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 45 ms 5952 KB Output is correct
3 Correct 41 ms 5516 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 58 ms 7756 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 76 ms 9652 KB Output is correct
9 Correct 91 ms 10040 KB Output is correct
10 Correct 103 ms 13104 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 98 ms 12692 KB Output is correct
15 Correct 87 ms 9376 KB Output is correct
16 Correct 98 ms 12700 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 99 ms 12788 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 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 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 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 70 ms 7960 KB Output is correct
3 Correct 67 ms 8000 KB Output is correct
4 Correct 108 ms 10992 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 70 ms 7960 KB Output is correct
3 Correct 67 ms 8000 KB Output is correct
4 Correct 108 ms 10992 KB Output is correct
5 Correct 98 ms 12660 KB Output is correct
6 Correct 97 ms 12048 KB Output is correct
7 Correct 96 ms 12064 KB Output is correct
8 Correct 93 ms 12192 KB Output is correct
9 Correct 67 ms 7996 KB Output is correct
10 Correct 92 ms 11764 KB Output is correct
11 Correct 91 ms 11404 KB Output is correct
12 Correct 69 ms 8256 KB Output is correct
13 Correct 69 ms 8864 KB Output is correct
14 Correct 73 ms 8688 KB Output is correct
15 Correct 73 ms 8760 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 55 ms 7580 KB Output is correct
18 Correct 68 ms 8284 KB Output is correct
19 Correct 96 ms 8244 KB Output is correct
20 Correct 103 ms 11924 KB Output is correct
21 Correct 89 ms 11424 KB Output is correct
22 Correct 90 ms 11588 KB Output is correct