oj.uz

답안 #1060221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1060221 2024-08-15T11:40:31 Z jamjanek 자동 인형 (IOI18_doll) C++14
100 / 100
 148 ms 23532 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;

int liscie[1000010];
map<int, int>mapa;
bool czy[1000010];
void create_circuit(int m, std::vector<int> A) {
	A.push_back(0);
	int n = A.size(), i;
	int base = 1;
	int log = 1;
	while(base<n){
		base*=2;
		log++;
	}
	vector<int>pozycje;
	for(i=0;i<base;i++){
		int x = i;
		int res = 0;
		int pom = base/2;
		while(x>0){
			if(x%2)res+=pom;
			pom/=2;
			x/=2;
		}
		if(res>=base-n)
			pozycje.push_back(res);
	}
	for(i=0;i<base;i++)liscie[i] = -1;
	for(i=0;i<n;i++){
		liscie[pozycje[i]] = A[i];
	}
	//for(auto j: pozycje)printf("%d ", j);printf("\n");
	vector<int>C(m+1, -1);
	vector<int>X,Y;
	for(i=1;i<base;i++){
		mapa[i] = i;
		if(i*2<base){
			X.push_back(-(i*2));
			Y.push_back(-(i*2+1));
		}
		else{
			X.push_back(liscie[i*2-base]);
			Y.push_back(liscie[i*2+1-base]);
		}
	}
	//answer(C, X, Y);return;

//	for(i=0;i<base;i++)printf("%d ", liscie[i]);
	for(i=base-1;i>=1;i--){
		if(i*2>=base)
			czy[i] = (liscie[i*2+1-base]!=-1);
		else
			czy[i] = czy[i*2]|czy[i*2+1];
		if(!czy[i]){
			mapa.erase(i);
		}
	}
//	for(i=1;i<base;i++)printf("%d\n", czy[i]);
	int it=1;
	for(auto &j: mapa){
		j.second = it++;
//		printf("%d %d\n", j.first, j.second);
	}
	vector<int>X1, Y1;
	for(int i=1;i<base;i++){
		if(mapa.find(i)!=mapa.end()){
			if(i*2>=base){
				X1.push_back(X[i-1]);
				Y1.push_back(Y[i-1]);
				continue;				
			}
			if(czy[i*2])
				X1.push_back(-mapa[-X[i-1]]);
			else
				X1.push_back(-1);

			if(czy[i*2+1])
				Y1.push_back(-mapa[-Y[i-1]]);
			else
				Y1.push_back(-1);
		}
	}
//	for(auto j: X1)printf("%d ", j);printf("\n");
//	for(auto j: Y1)printf("%d ", j);printf("\n");
	answer(C, X1, Y1);
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 54 ms 11740 KB Output is correct
3 Correct 51 ms 11540 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 64 ms 13860 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 54 ms 11740 KB Output is correct
3 Correct 51 ms 11540 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 64 ms 13860 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 106 ms 20224 KB Output is correct
9 Correct 148 ms 20432 KB Output is correct
10 Correct 127 ms 23460 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 54 ms 11740 KB Output is correct
3 Correct 51 ms 11540 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 64 ms 13860 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 106 ms 20224 KB Output is correct
9 Correct 148 ms 20432 KB Output is correct
10 Correct 127 ms 23460 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 120 ms 23408 KB Output is correct
15 Correct 112 ms 20176 KB Output is correct
16 Correct 137 ms 23276 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 126 ms 23532 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 105 ms 20052 KB Output is correct
3 Correct 106 ms 19888 KB Output is correct
4 Correct 143 ms 23104 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 105 ms 20052 KB Output is correct
3 Correct 106 ms 19888 KB Output is correct
4 Correct 143 ms 23104 KB Output is correct
5 Correct 121 ms 23360 KB Output is correct
6 Correct 122 ms 23364 KB Output is correct
7 Correct 121 ms 23176 KB Output is correct
8 Correct 119 ms 23284 KB Output is correct
9 Correct 102 ms 20008 KB Output is correct
10 Correct 124 ms 23168 KB Output is correct
11 Correct 131 ms 23108 KB Output is correct
12 Correct 103 ms 20000 KB Output is correct
13 Correct 102 ms 19920 KB Output is correct
14 Correct 106 ms 20180 KB Output is correct
15 Correct 105 ms 20180 KB Output is correct
16 Correct 3 ms 2904 KB Output is correct
17 Correct 70 ms 15692 KB Output is correct
18 Correct 105 ms 19920 KB Output is correct
19 Correct 100 ms 19996 KB Output is correct
20 Correct 136 ms 23104 KB Output is correct
21 Correct 117 ms 23256 KB Output is correct
22 Correct 119 ms 23132 KB Output is correct