oj.uz

Submission #79503

# Submission time Handle Problem Language Result Execution time Memory
79503 2018-10-14T16:52:04 Z admin Library (JOI18_library) C++17
0 / 100
 627 ms 9456 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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 588 KB number of queries: 2946.
2 Incorrect 56 ms 700 KB number of queries: 2911.
3 Incorrect 51 ms 724 KB number of queries: 3105.
4 Incorrect 44 ms 872 KB number of queries: 3070.
5 Incorrect 38 ms 880 KB number of queries: 3086.
6 Incorrect 53 ms 968 KB number of queries: 3092.
7 Incorrect 42 ms 968 KB number of queries: 3091.
8 Incorrect 46 ms 968 KB number of queries: 2957.
9 Incorrect 39 ms 968 KB number of queries: 3055.
10 Incorrect 21 ms 968 KB number of queries: 1833.
11 Incorrect 2 ms 968 KB number of queries: 0.
12 Incorrect 2 ms 968 KB number of queries: 13.
13 Incorrect 2 ms 968 KB number of queries: 16.
14 Incorrect 2 ms 968 KB number of queries: 29.
15 Incorrect 3 ms 968 KB number of queries: 139.
16 Incorrect 5 ms 968 KB number of queries: 290.

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 588 KB number of queries: 2946.
2 Incorrect 56 ms 700 KB number of queries: 2911.
3 Incorrect 51 ms 724 KB number of queries: 3105.
4 Incorrect 44 ms 872 KB number of queries: 3070.
5 Incorrect 38 ms 880 KB number of queries: 3086.
6 Incorrect 53 ms 968 KB number of queries: 3092.
7 Incorrect 42 ms 968 KB number of queries: 3091.
8 Incorrect 46 ms 968 KB number of queries: 2957.
9 Incorrect 39 ms 968 KB number of queries: 3055.
10 Incorrect 21 ms 968 KB number of queries: 1833.
11 Incorrect 2 ms 968 KB number of queries: 0.
12 Incorrect 2 ms 968 KB number of queries: 13.
13 Incorrect 2 ms 968 KB number of queries: 16.
14 Incorrect 2 ms 968 KB number of queries: 29.
15 Incorrect 3 ms 968 KB number of queries: 139.
16 Incorrect 5 ms 968 KB number of queries: 290.
17 Incorrect 625 ms 9448 KB number of queries: 18654.
18 Incorrect 601 ms 9448 KB number of queries: 18415.
19 Incorrect 623 ms 9456 KB number of queries: 18642.
20 Incorrect 545 ms 9456 KB number of queries: 17502.
21 Incorrect 509 ms 9456 KB number of queries: 16534.
22 Incorrect 594 ms 9456 KB number of queries: 18628.
23 Incorrect 584 ms 9456 KB number of queries: 18603.
24 Incorrect 194 ms 9456 KB number of queries: 9000.
25 Incorrect 627 ms 9456 KB number of queries: 18183.
26 Incorrect 530 ms 9456 KB number of queries: 17129.
27 Incorrect 162 ms 9456 KB number of queries: 8756.
28 Incorrect 548 ms 9456 KB number of queries: 17635.
29 Incorrect 538 ms 9456 KB number of queries: 17686.
30 Incorrect 553 ms 9456 KB number of queries: 17635.