| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 130209 |
2019-07-14T09:09:54 Z |
RockyB |
Library (JOI18_library) |
C++17 |
|
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++)
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
