oj.uz

Submission #838077

# Submission time Handle Problem Language Result Execution time Memory
838077 2023-08-26T07:57:18 Z tolbi Mechanical Doll (IOI18_doll) C++17
100 / 100
 112 ms 14932 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define coutarr(x) for(auto &it : x) cout<<it<<" ";cout<<endl;
#define tol(bi) (1LL<<((long long)(bi)))
void create_circuit(int M, vector<int> A) {
	int n = A.size();
	vector<int> X(tol(ceil(log2(n+1)))-1);
	vector<int> Y(X.size());
	int S = X.size();
	int cnt = n+1;
	for (int i = S-1; i >= 0; i--){
		X[i]=(i+1)*2;
		Y[i]=(i+1)*2+1;
		if (Y[i]>S){
			if (cnt) Y[i]=n+1-(cnt--);
			else Y[i]=-1;
		}
		else Y[i]=-Y[i];
		if (X[i]>S){
			if (cnt) X[i]=n+1-(cnt--);
			else X[i]=-1;
		}
		else X[i]=-X[i];
	}
	vector<bool> gerekli(S,false);
	for (int i = S-1; i >= 0; i--){
		if (X[i]>=0 || Y[i]>=0 || (X[i]<0 && Y[i]<0 && (gerekli[(-X[i])-1] || gerekli[(-Y[i])-1]))) gerekli[i]=true;
	}
	cnt=1;
	vector<int> gercek(S,-1);
	vector<int> x;
	vector<int> y;
	for (int i = 0; i < S; ++i)
	{
		if (gerekli[i]){
			gercek[i]=cnt++;
		}
	}
	for (int i = 0; i < S; i++){
		if (!gerekli[i]) continue;
		if (X[i]>=-1){
			x.push_back(X[i]);
			y.push_back(Y[i]);
			continue;
		}
		int xv = gercek[(-X[i])-1];
		int yv = gercek[(-Y[i])-1];
		if (xv!=-1) xv=-xv;
		if (yv!=-1) yv=-yv;
		x.push_back(xv);
		y.push_back(yv);
	}
	vector<int> C(M+1,-1);
	vector<int> gez;
	int node = -1;
	vector<int> state(S,0);
	while (gez.size()<n){
		if (node>=0){
			gez.push_back(node);
			node=-1;
		}
		else {
			node=-node-1;
			if (state[node]==0) state[node]=1;
			else state[node]=0;
			if (state[node]==1){
				node=x[node];
			}
			else node=y[node];
		}
	}
	vector<int> val(n+1);
	for (int i = 0; i < n; ++i)
	{
		val[gez[i]]=A[i];
	}
	for (int i = 0; i < S; i++){
		if (x[i]>0) x[i]=val[x[i]];
		if (y[i]>0) y[i]=val[y[i]];
	}
	answer(C,x,y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:58:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |  while (gez.size()<n){
      |         ~~~~~~~~~~^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 39 ms 6804 KB Output is correct
3 Correct 37 ms 6128 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 54 ms 8276 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 39 ms 6804 KB Output is correct
3 Correct 37 ms 6128 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 54 ms 8276 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 71 ms 11444 KB Output is correct
9 Correct 75 ms 11644 KB Output is correct
10 Correct 112 ms 14932 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 39 ms 6804 KB Output is correct
3 Correct 37 ms 6128 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 54 ms 8276 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 71 ms 11444 KB Output is correct
9 Correct 75 ms 11644 KB Output is correct
10 Correct 112 ms 14932 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 105 ms 14436 KB Output is correct
15 Correct 70 ms 10860 KB Output is correct
16 Correct 106 ms 14292 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 105 ms 14632 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 300 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 66 ms 10148 KB Output is correct
3 Correct 67 ms 9840 KB Output is correct
4 Correct 98 ms 12648 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 66 ms 10148 KB Output is correct
3 Correct 67 ms 9840 KB Output is correct
4 Correct 98 ms 12648 KB Output is correct
5 Correct 104 ms 12908 KB Output is correct
6 Correct 102 ms 12804 KB Output is correct
7 Correct 102 ms 12904 KB Output is correct
8 Correct 100 ms 12628 KB Output is correct
9 Correct 66 ms 9752 KB Output is correct
10 Correct 100 ms 12644 KB Output is correct
11 Correct 98 ms 12584 KB Output is correct
12 Correct 66 ms 9840 KB Output is correct
13 Correct 68 ms 10372 KB Output is correct
14 Correct 68 ms 10024 KB Output is correct
15 Correct 71 ms 10076 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 60 ms 7824 KB Output is correct
18 Correct 66 ms 10268 KB Output is correct
19 Correct 69 ms 9832 KB Output is correct
20 Correct 103 ms 12572 KB Output is correct
21 Correct 102 ms 12624 KB Output is correct
22 Correct 100 ms 12684 KB Output is correct