oj.uz

Submission #702389

# Submission time Handle Problem Language Result Execution time Memory
702389 2023-02-23T21:11:52 Z urosk Library (JOI18_library) C++14
100 / 100
 511 ms 476 KB 
#include "library.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

using namespace std;
#define maxn 1005
ll n;
vector<ll> use;
vector<ll> ril;
vector<ll> ans;
bool ok[maxn];
ll ask(){
    return Query(use);
}
ll ask(vector<ll> v){
    if(v.empty()) return 0;
    for(ll i = 0;i<n;i++) use[i] = 0;
    for(ll x : v) use[x] = 1;
    return Query(use);
}
void Solve(int N){
    n = N;
    use.assign(n,0);
    ans.resize(n);
    ll l = 0,r = n-1;
    vector<ll> v,v0,v1,w,wc;
    set<ll> s;
    while(l<=r){
        v.clear();
        for(ll i = 0;i<n;i++) if(!ok[i]) v.pb(i);
        if(l==r){ans[l] = v[0];break;}
        ll c = 0;
        for(ll i = 0;i<10;i++){
            v0.clear(); v1.clear();
            for(ll x : v){
                if((1<<i)&x) v1.pb(x);
                else v0.pb(x);
            }
            ll x0 = ask(v0),x1 = ask(v1);
            if(x1==x0) c+=(1<<i);
        }
        s.clear();
        w.clear();
        wc.clear();
        for(ll x : v){
            if(s.count(x^c)==0) s.insert(x);
            else wc.pb(x);
        }
        for(ll x : s) w.pb(x);
        ll tl = 0,tr = w.size()-1,mid,rez = 1;
        while(tl<=tr){
            mid = (tl+tr)/2;
            v0.clear();
            v1.clear();
            for(ll x : wc) v0.pb(x);
            for(ll i = 0;i<=mid;i++) v0.pb(w[i]);
            for(ll i = mid+1;i<w.size();i++) v1.pb(w[i]);
            ll x0 = ask(v0),x1 = ask(v1);
            if(abs(x0-x1)==1){
                rez = mid;
                tr = mid-1;
            }else tl = mid+1;
        }
        ll a = w[rez],b = w[rez]^c;
        if(l==0&&r==n-1){
            ans[l] = a,ans[r] = b;
        }else{
            v0.clear(); v0.pb(a); v0.pb(ans[l-1]);
            if(ask(v0)==1) ans[l] = a,ans[r] = b;
            else ans[r] = a,ans[l] = b;
        }
        ok[a] = ok[b] = 1;
        l++; r--;
    }
    for(ll &x : ans) x++;
    Answer(ans);
}
/**
5
4
2
5
3
1

3
1
4
2
0
**/

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:71:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for(ll i = mid+1;i<w.size();i++) v1.pb(w[i]);
      |                              ~^~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 208 KB # of queries: 2945
2 Correct 41 ms 320 KB # of queries: 2911
3 Correct 66 ms 324 KB # of queries: 3103
4 Correct 43 ms 208 KB # of queries: 3069
5 Correct 47 ms 328 KB # of queries: 3085
6 Correct 55 ms 336 KB # of queries: 3090
7 Correct 45 ms 320 KB # of queries: 3089
8 Correct 40 ms 304 KB # of queries: 2957
9 Correct 46 ms 328 KB # of queries: 3054
10 Correct 22 ms 208 KB # of queries: 1832
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 12
13 Correct 0 ms 208 KB # of queries: 15
14 Correct 1 ms 208 KB # of queries: 28
15 Correct 2 ms 208 KB # of queries: 138
16 Correct 5 ms 296 KB # of queries: 290

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 208 KB # of queries: 2945
2 Correct 41 ms 320 KB # of queries: 2911
3 Correct 66 ms 324 KB # of queries: 3103
4 Correct 43 ms 208 KB # of queries: 3069
5 Correct 47 ms 328 KB # of queries: 3085
6 Correct 55 ms 336 KB # of queries: 3090
7 Correct 45 ms 320 KB # of queries: 3089
8 Correct 40 ms 304 KB # of queries: 2957
9 Correct 46 ms 328 KB # of queries: 3054
10 Correct 22 ms 208 KB # of queries: 1832
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 12
13 Correct 0 ms 208 KB # of queries: 15
14 Correct 1 ms 208 KB # of queries: 28
15 Correct 2 ms 208 KB # of queries: 138
16 Correct 5 ms 296 KB # of queries: 290
17 Correct 476 ms 356 KB # of queries: 18652
18 Correct 352 ms 476 KB # of queries: 18414
19 Correct 511 ms 360 KB # of queries: 18640
20 Correct 434 ms 336 KB # of queries: 17500
21 Correct 397 ms 352 KB # of queries: 16534
22 Correct 470 ms 364 KB # of queries: 18625
23 Correct 478 ms 352 KB # of queries: 18602
24 Correct 153 ms 340 KB # of queries: 9000
25 Correct 504 ms 356 KB # of queries: 18182
26 Correct 492 ms 364 KB # of queries: 17129
27 Correct 171 ms 336 KB # of queries: 8755
28 Correct 479 ms 332 KB # of queries: 17634
29 Correct 377 ms 348 KB # of queries: 17686
30 Correct 485 ms 464 KB # of queries: 17634