oj.uz

Submission #1042894

# Submission time Handle Problem Language Result Execution time Memory
1042894 2024-08-03T14:13:46 Z ReLice Mechanical Doll (IOI18_doll) C++17
100 / 100
 110 ms 9836 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define ll int
#define vll vector<ll>
#define pb push_back
#define sz size()
using namespace std;
void create_circuit(int m, std::vector<int> a) {
	ll i;
	ll n = a.size();
	if(n==1){
		vll c(m+1,0);
		c[0]=a[0];
		answer(c,{},{});
		return;
	}
	vll c(m+1,-1);
	
	c[0]=a[0];
	a.erase(a.begin());
	a.pb(0);
	
	//~ for(auto i : a)cout<<i<<' ';
	//~ cout<<endl;
	
	ll bit=__lg(n);
	if((1ll<<bit) < n)bit++;
	
	vll x,y;
	auto get = [&](){
		x.pb(0);
		y.pb(0);
		return (ll)x.sz;
	};
	
	function<int(int,int,vector<int>)> build = [&](ll l,ll r,vll a){
		if(a.size()==0)return -1;
		if(l==r){
			assert(a.size()==1);
			return a[0];
		}
		ll m=(l+r)/2;
		ll goLeft=max(0,(ll)a.size()-(r-m));
		
		vll toL,toR;
		for(i=0;i<goLeft;i++){
			toL.pb(a[i]);
		}
		for(i=goLeft;i<(ll)a.size();i++){
			toR.pb(a[i]);
		}
		
		ll root=get();
		
		x[root-1]=build(l,m,toL);
		y[root-1]=build(m+1,r,toR);
		
		//~ cout<<-root<<' '<<x[root-1]<<' '<<y[root-1]<<endl;
		
		return -root; 
	};
	
	build(0,(1ll<<bit)-1,a);
	
	vector<bool> f((ll)x.size()+5,0);
	
	function<int(int, int)> simulate = [&](ll root,ll value){
		if(root>=0) return value;
		
		root=-root;
		
		f[root-1]=!f[root-1];
		if(f[root-1]){
			x[root-1]=simulate(x[root-1],value);
		}else{
			y[root-1]=simulate(y[root-1],value);
		}
		
		return -root;
	};
	
	for(i=0;i<n;i++){
		simulate(-1,a[i]);
	}
	
	answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 35 ms 4260 KB Output is correct
3 Correct 36 ms 4300 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 51 ms 5512 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 35 ms 4260 KB Output is correct
3 Correct 36 ms 4300 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 51 ms 5512 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 71 ms 6504 KB Output is correct
9 Correct 73 ms 7696 KB Output is correct
10 Correct 102 ms 9836 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 35 ms 4260 KB Output is correct
3 Correct 36 ms 4300 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 51 ms 5512 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 71 ms 6504 KB Output is correct
9 Correct 73 ms 7696 KB Output is correct
10 Correct 102 ms 9836 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 102 ms 9632 KB Output is correct
15 Correct 74 ms 7164 KB Output is correct
16 Correct 106 ms 9244 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 105 ms 9532 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 436 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 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 68 ms 5660 KB Output is correct
3 Correct 66 ms 7444 KB Output is correct
4 Correct 96 ms 9276 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 68 ms 5660 KB Output is correct
3 Correct 66 ms 7444 KB Output is correct
4 Correct 96 ms 9276 KB Output is correct
5 Correct 100 ms 9276 KB Output is correct
6 Correct 103 ms 9540 KB Output is correct
7 Correct 110 ms 9204 KB Output is correct
8 Correct 96 ms 9252 KB Output is correct
9 Correct 71 ms 7412 KB Output is correct
10 Correct 96 ms 9272 KB Output is correct
11 Correct 100 ms 9016 KB Output is correct
12 Correct 67 ms 7440 KB Output is correct
13 Correct 75 ms 5900 KB Output is correct
14 Correct 67 ms 7448 KB Output is correct
15 Correct 66 ms 7440 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 64 ms 5792 KB Output is correct
18 Correct 62 ms 5652 KB Output is correct
19 Correct 71 ms 7444 KB Output is correct
20 Correct 102 ms 9240 KB Output is correct
21 Correct 100 ms 9152 KB Output is correct
22 Correct 97 ms 9284 KB Output is correct