oj.uz

답안 #80717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
80717 2018-10-22T04:32:03 Z admin 도서관 (JOI18_library) C++17
100 / 100
 243 ms 832 KB 
#include "library.h"
 
#include <bits/stdc++.h>
 
using namespace std;
 
vector <vector <int>> G;
int g;
 
void Solve(int N)
{
	int i, j, cnt, q;
	vector <int> ask(N);
	
	for(i=0;i<N;i++){
		for(j=0;j<=i;j++) ask[j] = 1;
		q = Query(ask);
		for(j=0;j<=i;j++) ask[j] = 0;
		
		if(q == g + 1){
			// new group
			vector <int> v = {i};
			G.push_back(v);
			
			g ++;
		}
		else if(g == q){
			// endpoint
			int k, b;
			k = 0;
			
			ask[i] = 1;
			for(b=0;(1<<b)<g;b++){
				cnt = 0;
				for(j=0;j<g;j++) if(j & (1 << b)){
					for(auto &t: G[j]) ask[t] = 1;
					cnt ++;
				}
				
				q = Query(ask);
				if(q == cnt) k |= 1 << b;
				
				for(j=0;j<g;j++) if(j & (1 << b)){
					for(auto &t: G[j]) ask[t] = 0;
				}
			}
			ask[i] = 0;
			
			for(auto &t: G[k]) ask[t] = 1;
			ask[G[k].back()] = 0;
			ask[i] = 1;
			
			q = Query(ask);
			if(q == 1) reverse(G[k].begin(), G[k].end());
			G[k].push_back(i);
			
			for(auto &t: G[k]) ask[t] = 0;
			ask[i] = 0;
		}
		else{
			// merge two groups
			int k1, k2, t1, t2, b, f, f1, f2, nf;
			k1 = k2 = f1 = f2 = nf = 0; f = -1;
			
			ask[i] = 1;
			for(b=0;(1<<b)<g;b++){
				cnt = 0;
				for(j=0;j<g;j++) if(j & (1 << b)){
					for(auto &t: G[j]) ask[t] = 1;
					cnt ++;
				}
				
				q = Query(ask);
				if(q == cnt - 1) k1 |= 1 << b, k2 |= 1 << b;
				else if(q == cnt){
					if(f == -1) k1 |= 1 << b, f = 0;
					else f |= 1 << b;
				}
				else nf |= 1 << b;
				
				for(j=0;j<g;j++) if(j & (1 << b)){
					for(auto &t: G[j]) ask[t] = 0;
				}
			}
			ask[i] = 0;
			
			if(f != -1){
				ask[i] = 1;
				for(b=0;(1<<b)<g;b++) if(f & (1 << b)){
					cnt = 0;
					for(j=0;j<g;j++) if((j & k1) == k1 && (j & nf) == 0 && (j & (1 << b))){
						t1 = j; t2 = k2 | ((~j) & f);
						if(t2 >= g) continue;
						for(auto &t: G[t1]) ask[t] = 1;
						for(auto &t: G[t2]) ask[t] = 1;
						cnt += 2;
					}
					
					q = Query(ask);
					if(q == cnt - 1) f1 |= 1 << b;
					else f2 |= 1 << b;
					
					for(j=0;j<g;j++) if((j & k1) == k1 && (j & nf) == 0 && (j & (1 << b))){
						t1 = j; t2 = k2 | ((~j) & f);
						if(t2 >= g) continue;
						for(auto &t: G[t1]) ask[t] = 0;
						for(auto &t: G[t2]) ask[t] = 0;
					}
				}
				ask[i] = 0;
			}
			
			k1 |= f1; k2 |= f2;
			if(k1 >= g || k2 >= g) while(1);
			
			for(auto &t: G[k1]) ask[t] = 1;
			ask[G[k1].back()] = 0;
			ask[i] = 1;
			
			q = Query(ask);
			if(q == 1) reverse(G[k1].begin(), G[k1].end());
			
			for(auto &t: G[k1]) ask[t] = 0;
			ask[i] = 0;
			
			for(auto &t: G[k2]) ask[t] = 1;
			ask[G[k2].back()] = 0;
			ask[i] = 1;
			
			q = Query(ask);
			if(q == 2) reverse(G[k2].begin(), G[k2].end());
			
			for(auto &t: G[k2]) ask[t] = 0;
			ask[i] = 0;
			
			G[k1].push_back(i);
			for(auto &t: G[k2]) G[k1].push_back(t);
			G[k2].clear(); swap(G[k2], G.back());
			G.pop_back();
			
			g --;
		}
	}
	
	for(auto &t : G[0]) t ++;
	
	Answer(G[0]);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 316 KB # of queries: 1151
2 Correct 14 ms 356 KB # of queries: 1172
3 Correct 17 ms 412 KB # of queries: 1210
4 Correct 21 ms 416 KB # of queries: 1233
5 Correct 20 ms 432 KB # of queries: 1207
6 Correct 24 ms 436 KB # of queries: 1229
7 Correct 22 ms 624 KB # of queries: 1246
8 Correct 15 ms 624 KB # of queries: 1174
9 Correct 15 ms 624 KB # of queries: 1199
10 Correct 12 ms 624 KB # of queries: 707
11 Correct 2 ms 624 KB # of queries: 1
12 Correct 2 ms 624 KB # of queries: 3
13 Correct 2 ms 624 KB # of queries: 5
14 Correct 2 ms 624 KB # of queries: 8
15 Correct 2 ms 624 KB # of queries: 48
16 Correct 3 ms 624 KB # of queries: 104

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 316 KB # of queries: 1151
2 Correct 14 ms 356 KB # of queries: 1172
3 Correct 17 ms 412 KB # of queries: 1210
4 Correct 21 ms 416 KB # of queries: 1233
5 Correct 20 ms 432 KB # of queries: 1207
6 Correct 24 ms 436 KB # of queries: 1229
7 Correct 22 ms 624 KB # of queries: 1246
8 Correct 15 ms 624 KB # of queries: 1174
9 Correct 15 ms 624 KB # of queries: 1199
10 Correct 12 ms 624 KB # of queries: 707
11 Correct 2 ms 624 KB # of queries: 1
12 Correct 2 ms 624 KB # of queries: 3
13 Correct 2 ms 624 KB # of queries: 5
14 Correct 2 ms 624 KB # of queries: 8
15 Correct 2 ms 624 KB # of queries: 48
16 Correct 3 ms 624 KB # of queries: 104
17 Correct 197 ms 624 KB # of queries: 7855
18 Correct 192 ms 624 KB # of queries: 7819
19 Correct 243 ms 696 KB # of queries: 7846
20 Correct 179 ms 832 KB # of queries: 7336
21 Correct 168 ms 832 KB # of queries: 6959
22 Correct 202 ms 832 KB # of queries: 7913
23 Correct 228 ms 832 KB # of queries: 7856
24 Correct 69 ms 832 KB # of queries: 3666
25 Correct 190 ms 832 KB # of queries: 7706
26 Correct 206 ms 832 KB # of queries: 7260
27 Correct 74 ms 832 KB # of queries: 3619
28 Correct 80 ms 832 KB # of queries: 1999
29 Correct 47 ms 832 KB # of queries: 1997
30 Correct 54 ms 832 KB # of queries: 1999