Submission #702389

#	Time	Username	Problem	Language	Result	Execution time	Memory
702389		urosk	Library (JOI18_library)	C++14	100 / 100	511 ms	476 KiB

library

#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 (stderr)

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 / 19
• Subtask 2: 81 / 81