제출 #80717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
80717		admin	도서관 (JOI18_library)	C++17	100 / 100	243 ms	832 KiB

library

#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 / 19
• Subtask 2: 81 / 81