oj.uz

Submission #838053

# Submission time Handle Problem Language Result Execution time Memory
838053 2023-08-26T07:19:37 Z tolbi Mechanical Doll (IOI18_doll) C++17
37 / 100
 120 ms 14444 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;
	for (int i = 0; i < S; i++){
		X[i]=(i+1)*2;
		Y[i]=(i+1)*2+1;
		if (X[i]>S){
			if (cnt) X[i]=n+1-(cnt--);
			else X[i]=-1;
		}
		else X[i]=-X[i];
		if (Y[i]>S){
			if (cnt) Y[i]=n+1-(cnt--);
			else Y[i]=-1;
		}
		else Y[i]=-Y[i];
	}
	Y.back()=0;
	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:59:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |  while (gez.size()<n){
      |         ~~~~~~~~~~^~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 85 ms 12064 KB Output is partially correct
3 Partially correct 87 ms 12280 KB Output is partially correct
4 Partially correct 106 ms 14152 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 85 ms 12064 KB Output is partially correct
3 Partially correct 87 ms 12280 KB Output is partially correct
4 Partially correct 106 ms 14152 KB Output is partially correct
5 Partially correct 120 ms 14444 KB Output is partially correct
6 Partially correct 114 ms 14240 KB Output is partially correct
7 Partially correct 112 ms 14284 KB Output is partially correct
8 Partially correct 115 ms 14176 KB Output is partially correct
9 Partially correct 85 ms 12272 KB Output is partially correct
10 Partially correct 108 ms 14240 KB Output is partially correct
11 Partially correct 119 ms 14108 KB Output is partially correct
12 Partially correct 84 ms 12268 KB Output is partially correct
13 Partially correct 86 ms 12908 KB Output is partially correct
14 Partially correct 90 ms 12556 KB Output is partially correct
15 Partially correct 89 ms 12656 KB Output is partially correct
16 Partially correct 3 ms 724 KB Output is partially correct
17 Correct 63 ms 8392 KB Output is correct
18 Partially correct 86 ms 12856 KB Output is partially correct
19 Partially correct 85 ms 12320 KB Output is partially correct
20 Partially correct 115 ms 14188 KB Output is partially correct
21 Partially correct 109 ms 14248 KB Output is partially correct
22 Partially correct 108 ms 14192 KB Output is partially correct