oj.uz

답안 #198709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198709 2020-01-27T12:44:56 Z SuperJava 자동 인형 (IOI18_doll) C++17
100 / 100
 236 ms 25388 KB 
#include "doll.h"
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
#include <map>
#define sz(A) int(A.size())
using namespace std;

vector<int> adj[200005];
vector<int> v = {2,4,8,16,32,64,128,256,512,1024,2048,
				4096,8192,16384,32768,65536,131072,
				262144};

int dig(int x){
	int ans = 0;
	while(x != 1){
		x /= 2;
		ans++;
	}
	return ans;
}

void create_circuit(int M, vector<int> A) {
	for(int i = 0; i < sz(A); i++){
		adj[0].push_back(A[i]);
	}
	adj[0].push_back(0);
	vector<int> C(M+1);
	vector<int> X,Y;
	for(int i = 1; i <= M; i++){
		C[i] = -1;
	}
	for(int i = 0; i <= 1; i++){
		int w = sz(adj[i]);
		if(w == 0) continue;
		if(w == 1){
			C[i] = adj[i][0];
			continue;
		}
		if(w == 2){
			C[i] = -(sz(X)+1);
			X.push_back(adj[i][0]);
			Y.push_back(adj[i][1]);
			continue;
		}
		if((w&(w-1))){
			C[i] = -(sz(X)+1);
			int fulen = *lower_bound(v.begin(), v.end(),w);
			vector<pair<int,int>> news(fulen-1);
			for(int j = 0; j < fulen/2-1; j++){
				news[j].first = -(j+1)*2-sz(X);
				news[j].second = -(j+1)*2-sz(X)-1;
			}
			int digits = dig(fulen);
			vector<int> toadd(w);
			for(int j = 0; j < w; j++){
				toadd[j] = adj[i][j];
			}
			vector<int> qw;
			for(int j = 0; j < fulen; j++){
				int res = 0;
				for(int k = 0; k < digits; k++){
					res += (1<<k)*((j&(1<<(digits-k-1))) > 0);
				}
				qw.push_back(res);
			}
			for(int j = 0; j < fulen-w; j++){
				if(j&1){
					news[j/2+fulen/2-1].second = -(sz(X)+1);
				}else{
					news[j/2+fulen/2-1].first = -(sz(X)+1);
				}
			}
			vector<pair<int,int>> ss;
			for(int j = fulen-w; j < fulen; j++){
				ss.push_back({qw[j],j});
			}
			sort(ss.begin(), ss.end());
			for(int j = 0; j < w; j++){
				if(ss[j].second&1){
					news[(ss[j].second/2+fulen/2-1)].second = toadd[j];
				}else{
					news[(ss[j].second/2+fulen/2-1)].first = toadd[j];
				}
			}
			for(int j = fulen-2; j >= 0; j--){
				if(news[j].first == -(sz(X)+1) && news[j].second == -(sz(X)+1)){
					if(j&1){
						news[(j+1)/2-1].first = -(sz(X)+1);
					}else{
						news[(j+1)/2-1].second = -(sz(X)+1);
					}
				}
			}
			map<int,int> m;
			int counter = -(sz(X)+1);
			for(int j = 0; j < sz(news); j++){
				if(news[j].first == -(sz(X)+1) && news[j].second == -(sz(X)+1)) continue;
				m[-j-(sz(X)+1)] = counter--;
			}
			for(int j = 0; j < sz(news); j++){
				if(news[j].first == -(sz(X)+1) && news[j].second == -(sz(X)+1)) continue;
				if(news[j].first < 0) news[j].first = m[news[j].first];
				if(news[j].second < 0) news[j].second = m[news[j].second];
			}
			for(int j = 0; j < sz(news); j++){
				if(news[j].first == -(sz(X)+1) && news[j].second == -(sz(X)+1)) continue;
//				cout << news[j].first << " " << news[j].second << endl;
			}
			int re = -(sz(X)+1);
			for(int j = 0; j < fulen-1; j++){
				if(news[j].first == re && news[j].second == re) continue;
				X.push_back(news[j].first);
				Y.push_back(news[j].second);
			}
		}else{
			C[i] = -(sz(X)+1);
			int fulen = *lower_bound(v.begin(), v.end(),w);
			vector<pair<int,int>> news(fulen-1);
			for(int j = 0; j < fulen/2-1; j++){
				news[j].first = -(j+1)*2-sz(X);
				news[j].second = -(j+1)*2-sz(X)-1;
			}
			int digits = dig(fulen);
			vector<int> toadd(fulen);
			for(int j = 0; j < w; j++){
				toadd[j] = adj[i][j];
			}
			for(int j = 0; j < fulen; j++){
				int res = 0;
				for(int k = 0; k < digits; k++){
					res += (1<<k)*((j&(1<<(digits-k-1))) > 0);
				}
				if(res&1){
					news[res/2+fulen/2-1].second = toadd[j];
				}else{
					news[res/2+fulen/2-1].first = toadd[j];
				}
			}
			
			for(int j = 0; j < fulen-1; j++){
				X.push_back(news[j].first);
				Y.push_back(news[j].second);
			}
		}
	}
	answer(C,X,Y);
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 82 ms 12556 KB Output is correct
3 Correct 63 ms 12480 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 14 ms 6092 KB Output is correct
6 Correct 107 ms 15168 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 82 ms 12556 KB Output is correct
3 Correct 63 ms 12480 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 14 ms 6092 KB Output is correct
6 Correct 107 ms 15168 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 120 ms 19956 KB Output is correct
9 Correct 126 ms 20020 KB Output is correct
10 Correct 202 ms 25388 KB Output is correct
11 Correct 5 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 82 ms 12556 KB Output is correct
3 Correct 63 ms 12480 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 14 ms 6092 KB Output is correct
6 Correct 107 ms 15168 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 120 ms 19956 KB Output is correct
9 Correct 126 ms 20020 KB Output is correct
10 Correct 202 ms 25388 KB Output is correct
11 Correct 5 ms 4940 KB Output is correct
12 Correct 5 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 182 ms 25332 KB Output is correct
15 Correct 122 ms 19848 KB Output is correct
16 Correct 187 ms 25216 KB Output is correct
17 Correct 5 ms 4940 KB Output is correct
18 Correct 5 ms 4940 KB Output is correct
19 Correct 5 ms 4940 KB Output is correct
20 Correct 190 ms 25304 KB Output is correct
21 Correct 4 ms 4940 KB Output is correct
22 Correct 5 ms 4940 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 111 ms 19704 KB Output is correct
3 Correct 113 ms 19620 KB Output is correct
4 Correct 236 ms 25024 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 111 ms 19704 KB Output is correct
3 Correct 113 ms 19620 KB Output is correct
4 Correct 236 ms 25024 KB Output is correct
5 Correct 181 ms 25228 KB Output is correct
6 Correct 183 ms 25164 KB Output is correct
7 Correct 226 ms 25112 KB Output is correct
8 Correct 177 ms 25116 KB Output is correct
9 Correct 156 ms 19736 KB Output is correct
10 Correct 183 ms 25084 KB Output is correct
11 Correct 190 ms 25088 KB Output is correct
12 Correct 116 ms 19692 KB Output is correct
13 Correct 119 ms 19672 KB Output is correct
14 Correct 118 ms 19692 KB Output is correct
15 Correct 119 ms 19716 KB Output is correct
16 Correct 8 ms 5452 KB Output is correct
17 Correct 66 ms 9944 KB Output is correct
18 Correct 116 ms 19636 KB Output is correct
19 Correct 121 ms 19704 KB Output is correct
20 Correct 183 ms 25124 KB Output is correct
21 Correct 182 ms 25076 KB Output is correct
22 Correct 183 ms 25044 KB Output is correct