oj.uz

Submission #58179

# Submission time Handle Problem Language Result Execution time Memory
58179 2018-07-17T05:55:45 Z 김세빈(#1689) Library (JOI18_library) C++11
0 / 100
 2000 ms 248 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++){
//		printf("i : %d\n", i + 1);
		
		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
//			printf("new group\n");
			vector <int> v = {i};
			G.push_back(v);
			
			g ++;
		}
		else if(g == q){
			// endpoint
//			printf("endpoint\n");
			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
//			printf("merge two groups\n");
			int k1, k2, t1, t2, b, f;
			k1 = k2 = 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;
				}
				
				for(j=0;j<g;j++) if(j & (1 << b)){
					for(auto &t: G[j]) ask[t] = 0;
				}
			}
			ask[i] = 0;
			
			if(k1 >= g || k2 >= g) while(1);
			
			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 & (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) k1 |= 1 << b;
					else k2 |= 1 << b;
					
					for(j=0;j<g;j++) if((j & k1) == k1 && (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;
			}
			
			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;
			
//			printf("%d %d\n", k1, k2);
			
			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 &t1: G){
			for(auto &t2: t1) printf("%d ", t2 + 1);
			printf("\n");
		}
		
		printf("\n");
*/	}
	
	for(auto &t : G[0]) t ++;
	
	Answer(G[0]);
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2023 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2023 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -