oj.uz

Submission #983563

# Submission time Handle Problem Language Result Execution time Memory
983563 2024-05-15T17:49:30 Z shadow_sami Mechanical Doll (IOI18_doll) C++17
100 / 100
 323 ms 39260 KB 
#include<bits/stdc++.h>
#include "doll.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e5+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
ll a[mx];
ll xx[mx];
ll yy[mx];
ll cc[mx];
ll bt;
ll tim = 1;
ll b[mx];

void dnq(vi &vv,ll l,ll r){
	if(l==r)
		return;
	// debug(vv);
	// debug(l);
	// debug(r);
	fip(l,r+1)
		b[i] = vv[i];
	cnt = r - l + 1;
	res = l;
	fip(l,l+cnt/2){
		vv[i] = b[res];
		res += 2;
	}
	// debug(vv);
	res = l+1;
	fip(l+cnt/2,l+cnt){
		vv[i] = b[res];
		res += 2;
	}
	// debug(vv);
	dnq(vv,l,l+(r-l)/2);
	dnq(vv,l+(r-l)/2+1,r);
	return;
}

void get(ll id,vi v,ll k,ll pt){	
	tptp = max(id,tptp);
	// debug(id);
	// debug(v);
	if((pt+(ll)v.size())==1){		
		xx[id] = -1;
		yy[id] = a[v[0]];
		return;
	}else if((pt+(ll)v.size())==2){
		if(pt){
			xx[id] = -1;
			yy[id] = a[v[0]];
		}else{
			xx[id] = a[v[0]];
			yy[id] = a[v[1]];
		}
		// debug(yy[id]);
		return;
	}
	if(pt >= (1 << (k-1))){		
		xx[id] = -1;
		yy[id] = -tim-1;
		tim+=1;
		get(abs(yy[id]),v,k-1,pt-(1<<(k-1)));
	}else{
		vi vv;
		fip(0,(1<<k))
			vv.push_back(i);
		vi v2[2];			
		dnq(vv,0,(1<<k)-1);
		// debug(vv);
		vector<pi> pp;
		fip(pt,(1<<k))
			pp.push_back({vv[i],i});
		srt(pp);
		// debug(pp);
		fip(0,(ll)v.size()){
			if(pp[i].ss>=(1<<(k-1)))
				v2[1].push_back(v[i]);
			else
				v2[0].push_back(v[i]);
		}		
		
		// cerr<<nli;
		xx[id] = - tim - 1;
		yy[id] = - tim - 2;		
		tim+=2;
		get(abs(xx[id]),v2[0],k-1,pt);
		get(abs(yy[id]),v2[1],k-1,0);
	}
	return;
}

vi lis;

ll adj[mx][2];
ll adj2[mx][2];
ll id[mx];

// void dfs(ll u,ll par){
// 	// debug(n);
// 	if((ll)lis.size() > bt+1)
// 		return;
// 	// debug(u);
// 	// debug(par);
// 	// if(!par){
// 	// 	debug(adj2[u][0]);
// 	// 	debug(adj2[u][1]);
// 	// }
// 	// fip(1,tptp+1)
// 	// 	cerr<<id[i]<<" ";
// 	// cerr<<nli;
// 	// cerr<<nli;
// 	if(par)
// 		lis.push_back(u);
// 	if(par){
// 		dfs(abs(adj[u][0]),(adj[u][0] < 0?0:1));
// 	}
// 	else{
// 		id[u] ^= 1;

// 		dfs(abs(adj2[u][!id[u]]),(adj2[u][!id[u]] >= 0));		
// 	}

// 	return;
// }

// void answer(vector<int> c,vector<int> x,vector<int> y){
// 	n = c.size();
// 	debug(c);
// 	debug(x);
// 	debug(y);

	
// 	fip(0,n)
// 		adj[i][0] = c[i];
// 	fip(0,(ll)x.size()){
// 		adj2[i+1][0] = x[i];
// 		adj2[i+1][1] = y[i];
// 	}
// 	fip(0,(ll)x.size())
// 		id[i] = 0;
// 	dfs(0,1);
// 	fx(lis)
// 		cout<<x<<" ";
// 	cout<<nli;
// 	return;
// }

void create_circuit(int M, vector<int> A) {
	n = A.size();
	vi v;
	fip(0,n){
		a[i] = A[i];
		v.push_back(i);
	}
	a[n] = 0;
	v.push_back(n);
	m = M;
	vector<int> c,x,y;
	c.resize(m+1);
	for(auto &y : c){
		y = -1;	
	}
	res = 1;
	cnt = 0;
	tp2 = -1;
	while(n>=res){
		cnt++;
		res *= 2;
	}
	tp = res - n - 1;
	tptp = 0;
	get(1,v,cnt,tp);
	x.resize(tptp);
	y.resize(tptp);
	fip(0,tptp){
		x[i] = xx[i+1];
		y[i] = yy[i+1];
	}
	answer(c,x,y);
	return;
}

// int main(){
//     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//     #ifndef ONLINE_JUDGE
//         freopen("input1.txt", "r", stdin);
//         freopen("output1.txt", "w", stdout);
//         freopen("error1.txt", "w", stderr);
//     #endif // ONLINE_JUDGE

//         cin>>m>>n;
//         bt = n;
//         vector<int> aa(n);
//         fip(0,n)
//         	cin>>aa[i];
//        	create_circuit(m,aa);
        
//     cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
//     return 0;
// }

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 101 ms 20880 KB Output is correct
3 Correct 103 ms 20632 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 9 ms 11868 KB Output is correct
6 Correct 150 ms 22756 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 101 ms 20880 KB Output is correct
3 Correct 103 ms 20632 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 9 ms 11868 KB Output is correct
6 Correct 150 ms 22756 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 215 ms 33108 KB Output is correct
9 Correct 209 ms 33156 KB Output is correct
10 Correct 323 ms 39260 KB Output is correct
11 Correct 1 ms 10584 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 101 ms 20880 KB Output is correct
3 Correct 103 ms 20632 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 9 ms 11868 KB Output is correct
6 Correct 150 ms 22756 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 215 ms 33108 KB Output is correct
9 Correct 209 ms 33156 KB Output is correct
10 Correct 323 ms 39260 KB Output is correct
11 Correct 1 ms 10584 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 317 ms 38844 KB Output is correct
15 Correct 220 ms 33576 KB Output is correct
16 Correct 314 ms 38032 KB Output is correct
17 Correct 1 ms 10588 KB Output is correct
18 Correct 1 ms 10588 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 323 ms 38360 KB Output is correct
21 Correct 2 ms 10588 KB Output is correct
22 Correct 1 ms 10584 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 205 ms 33936 KB Output is correct
3 Correct 205 ms 33212 KB Output is correct
4 Correct 316 ms 38080 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 205 ms 33936 KB Output is correct
3 Correct 205 ms 33212 KB Output is correct
4 Correct 316 ms 38080 KB Output is correct
5 Correct 315 ms 38516 KB Output is correct
6 Correct 313 ms 38156 KB Output is correct
7 Correct 311 ms 38168 KB Output is correct
8 Correct 313 ms 38060 KB Output is correct
9 Correct 206 ms 33620 KB Output is correct
10 Correct 313 ms 38056 KB Output is correct
11 Correct 311 ms 37876 KB Output is correct
12 Correct 208 ms 34232 KB Output is correct
13 Correct 205 ms 33740 KB Output is correct
14 Correct 206 ms 33200 KB Output is correct
15 Correct 203 ms 32728 KB Output is correct
16 Correct 6 ms 11100 KB Output is correct
17 Correct 181 ms 23708 KB Output is correct
18 Correct 203 ms 32528 KB Output is correct
19 Correct 203 ms 33728 KB Output is correct
20 Correct 307 ms 38044 KB Output is correct
21 Correct 310 ms 38056 KB Output is correct
22 Correct 317 ms 38060 KB Output is correct