oj.uz

Submission #426355

# Submission time Handle Problem Language Result Execution time Memory
426355 2021-06-13T19:15:10 Z Pbezz Mechanical Doll (IOI18_doll) C++14
53 / 100
 125 ms 14632 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 2e5+5;
const ll INF = 1e9+7;

void create_circuit(int M, std::vector<int> A) {
	int n = A.size(),k,S=-1,i,j,bruh;

	vector<vector<int>>adj(M+5);
	std::vector<int> X, Y;
	std::vector<int> C(M + 1);
	C[0]=A[0];
	for(i=0;i<n-1;i++){
	//C[A[i]]=A[i+1];
	adj[A[i]].pb(A[i+1]);
}
	adj[A[n-1]].pb(0);

	for(i=1;i<=M;i++){
	k=adj[i].size(); S=-(X.size())-1;
//	cout<<i<<" #"<<k<<endl;
	if(k==1){
	C[i]=adj[i][0];
	}else if(k>=2){

	ll cur=1,mock=1; bruh=0;
	C[i] = S;
	while(cur<k){//new level com cur switches
//	cout<<cur<<"jj\n";
	for(j=0;j<cur;j++){

	if(2*cur<k){//ainda vai haver next
	X.pb(-(2*mock)+S+1);
	Y.pb(-(2*mock+1)+S+1);//cout<<-(2*mock)-1<<" "<<-(2*mock+1)-1<<endl;
	}else{

	ll a=mock,siga=0,po=bruh;
	while(po>0){po--;
	if(a&(1LL<<0))siga|=(1LL<<po);
	a/=2;
	}
	//cout<<siga<<" "<<cur<<endl;
	if(siga<k){
	X.pb(adj[i][siga]);
	}else{
	X.pb(C[i]);
	}
	if(siga+cur<k-1){
	Y.pb(adj[i][siga+cur]);
	}else if(siga+cur==2*cur-1){
	Y.pb(adj[i][k-1]);
	}else{
	Y.pb(C[i]);
	}

	}

	mock++;
	}


cur*=2;bruh++;
}
}


}
/*
	for(i=0;i<=M;i++)cout<<C[i]<<" ";
	cout<<endl;

	for(auto u:X)cout<<u<<" ";
	cout<<endl;
	for(auto u:Y)cout<<u<<" ";
	cout<<endl;
*/

	
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 33 ms 6348 KB Output is correct
3 Correct 34 ms 5076 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 3788 KB Output is correct
6 Correct 41 ms 7596 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 1 ms 204 KB Output is correct
2 Correct 33 ms 6348 KB Output is correct
3 Correct 34 ms 5076 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 3788 KB Output is correct
6 Correct 41 ms 7596 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 55 ms 7212 KB Output is correct
9 Correct 61 ms 8572 KB Output is correct
10 Correct 96 ms 11064 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 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 1 ms 204 KB Output is correct
2 Correct 33 ms 6348 KB Output is correct
3 Correct 34 ms 5076 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 3788 KB Output is correct
6 Correct 41 ms 7596 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 55 ms 7212 KB Output is correct
9 Correct 61 ms 8572 KB Output is correct
10 Correct 96 ms 11064 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 104 ms 10928 KB Output is correct
15 Correct 53 ms 6716 KB Output is correct
16 Correct 82 ms 10164 KB Output is correct
17 Correct 1 ms 292 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 288 KB Output is correct
20 Correct 97 ms 12056 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 53 ms 5192 KB Output is correct
3 Partially correct 81 ms 8044 KB Output is partially correct
4 Partially correct 90 ms 8900 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 53 ms 5192 KB Output is correct
3 Partially correct 81 ms 8044 KB Output is partially correct
4 Partially correct 90 ms 8900 KB Output is partially correct
5 Partially correct 117 ms 12104 KB Output is partially correct
6 Partially correct 123 ms 13948 KB Output is partially correct
7 Partially correct 116 ms 13740 KB Output is partially correct
8 Partially correct 125 ms 14216 KB Output is partially correct
9 Partially correct 79 ms 9724 KB Output is partially correct
10 Partially correct 121 ms 14476 KB Output is partially correct
11 Partially correct 119 ms 14632 KB Output is partially correct
12 Partially correct 77 ms 9688 KB Output is partially correct
13 Partially correct 80 ms 9264 KB Output is partially correct
14 Partially correct 77 ms 9092 KB Output is partially correct
15 Partially correct 72 ms 8832 KB Output is partially correct
16 Partially correct 2 ms 588 KB Output is partially correct
17 Partially correct 66 ms 8120 KB Output is partially correct
18 Partially correct 84 ms 8068 KB Output is partially correct
19 Partially correct 67 ms 8500 KB Output is partially correct
20 Partially correct 94 ms 11176 KB Output is partially correct
21 Partially correct 108 ms 12892 KB Output is partially correct
22 Partially correct 86 ms 10644 KB Output is partially correct