oj.uz

답안 #130209

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130209 2019-07-14T09:09:54 Z RockyB 도서관 (JOI18_library) C++17
100 / 100
 688 ms 9460 KB 
#include <cstdio>
#include <vector>
#include "library.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

vector<int> res;
set<int> rem;
int n;

int query(vector<int> &test)
{
	int ex1=0;
	for(int i=0;i<n;i++)
	{
		if(test[i]) ex1=1;
	}
	if(!ex1) return 0;
	else return Query(test);
}

void solve(int l, int r)
{
	//cerr<<"SOLVE "<<l<<' '<<r<<'\n';
	if(l>r) return ;
	if(l==r)
	{
		res[l] = (*rem.begin()); return ;
	}
	int xr=0;
	for(int i=0;i<10;i++)
	{
		vector<int> test(n,0);
		for(int x:rem)
		{
			if(x&(1<<i))
			{
				test[x]=1;
			}
		}
		int res = query(test);
		test.assign(n,0);
		for(int x:rem)
		{
			if(!(x&(1<<i)))
			{
				test[x]=1;
			}
		}
		int res2 = query(test);
		if(res==res2)
		{
			xr^=(1<<i);
		}
	}
	set<int> possibleX; vi V;
	for(int x:rem)
	{
		if(possibleX.find(x^xr)==possibleX.end())
		{
			possibleX.insert(x); V.pb(x);
		}
	}
	int lo=0; int hi=int(V.size())-1;
	int ans = -1;
	while(lo<=hi)
	{
		int mid=(lo+hi)>>1;
		vector<int> test(n,0);
		for(int i=0;i<V.size();i++)
		{
			if(i<=mid) test[V[i]]=1;
			else test[V[i]]=0;
		}
		int ans1 = query(test);
		for(int x:rem)
		{
			test[x]^=1;
		}
		int ans2=query(test);
		if(ans1==ans2)
		{
			ans=mid;
			hi=mid-1;
		}
		else lo=mid+1;
	}
	//cerr<<"XOR : "<<xr<<'\n'; //cerr<<"ANS : "<<ans<<'\n';
	int x = V[ans]; int y = V[ans]^xr;
	if(l>0)
	{
		vector<int> test(n,0);
		test[res[l-1]]=1; test[x]=1;
		if(query(test)!=1)
		{
			swap(x,y);
		}
	}
	res[l] = x; res[r] = y;
	//cerr<<l<<' '<<x<<'\n'; //cerr<<r<<' '<<y<<'\n';
	rem.erase(x); rem.erase(y);
	solve(l+1,r-1);
}

void Solve(int N)
{
	n=N;
	res.resize(N);
	for(int i=0;i<N;i++) rem.insert(i);
	solve(0,N-1);
	for(int i=0;i<N;i++) res[i]++;
	Answer(res);
}

Compilation message

library.cpp: In function 'void solve(int, int)':
library.cpp:89:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<V.size();i++)
               ~^~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 584 KB # of queries: 2946
2 Correct 65 ms 724 KB # of queries: 2911
3 Correct 67 ms 776 KB # of queries: 3105
4 Correct 46 ms 712 KB # of queries: 3070
5 Correct 52 ms 652 KB # of queries: 3086
6 Correct 55 ms 708 KB # of queries: 3092
7 Correct 69 ms 680 KB # of queries: 3091
8 Correct 62 ms 680 KB # of queries: 2957
9 Correct 67 ms 668 KB # of queries: 3055
10 Correct 38 ms 376 KB # of queries: 1833
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 13
13 Correct 2 ms 248 KB # of queries: 16
14 Correct 2 ms 376 KB # of queries: 29
15 Correct 4 ms 376 KB # of queries: 139
16 Correct 6 ms 376 KB # of queries: 290

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 584 KB # of queries: 2946
2 Correct 65 ms 724 KB # of queries: 2911
3 Correct 67 ms 776 KB # of queries: 3105
4 Correct 46 ms 712 KB # of queries: 3070
5 Correct 52 ms 652 KB # of queries: 3086
6 Correct 55 ms 708 KB # of queries: 3092
7 Correct 69 ms 680 KB # of queries: 3091
8 Correct 62 ms 680 KB # of queries: 2957
9 Correct 67 ms 668 KB # of queries: 3055
10 Correct 38 ms 376 KB # of queries: 1833
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 13
13 Correct 2 ms 248 KB # of queries: 16
14 Correct 2 ms 376 KB # of queries: 29
15 Correct 4 ms 376 KB # of queries: 139
16 Correct 6 ms 376 KB # of queries: 290
17 Correct 676 ms 9456 KB # of queries: 18654
18 Correct 686 ms 9256 KB # of queries: 18415
19 Correct 688 ms 9228 KB # of queries: 18642
20 Correct 638 ms 8644 KB # of queries: 17502
21 Correct 588 ms 7816 KB # of queries: 16534
22 Correct 660 ms 9388 KB # of queries: 18628
23 Correct 654 ms 9460 KB # of queries: 18603
24 Correct 200 ms 2584 KB # of queries: 9000
25 Correct 679 ms 8952 KB # of queries: 18183
26 Correct 616 ms 8208 KB # of queries: 17129
27 Correct 255 ms 2684 KB # of queries: 8756
28 Correct 606 ms 8136 KB # of queries: 17635
29 Correct 610 ms 8080 KB # of queries: 17686
30 Correct 631 ms 8168 KB # of queries: 17635