Submission #1015940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015940		hotboy2703	The Big Prize (IOI17_prize)	C++17	20 / 100	33 ms	3504 KiB

prize

#include "prize.h"
 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2e5+100;
pll a[MAXN];
ll ans = -1;
ll req = 0;
void query(ll i){
    if (a[i].fi==-1){
        vector <int> tmp = ask(i);
        a[i] = MP(tmp[0],tmp[1]);
        if (a[i].fi+a[i].se==0)ans = i;
    }
}
void solve(ll l,ll r,ll l1,ll r1){
//    cout<<l<<' '<<r<<' '<<l1<<' '<<r1<<endl;
    ll k=r1-l1;
    if (k==0)return;
    ll mid = (l + r) >> 1;
    ll id = -1;
    for (ll i = 0;i < k;i ++){
        ll cur_mid = mid + ((i+1)/2) * (i%2?1:-1);
        query(cur_mid);
        if (a[cur_mid].fi+a[cur_mid].se==req){
            id = i;
            break;
        }
    }
    if (id==-1)return;
    ll mid_l,mid_r;
    ll L,R;
    if (id%2){
        mid_r = mid + ((id+1)/2);
        mid_l = mid - ((id-1)/2);
        R = a[mid_r].fi;
        L = R-id;
    }
    else{
        mid_r = mid + (id/2);
        mid_l = mid - (id/2);
        L = a[mid_l].fi;
        R = L+id;
    }
    solve(l,mid_l-1,l1,L);
    solve(mid_r+1,r,R,r1);
}
mt19937_64 rng(694200);
int find_best(int n) {
    memset(a,-1,sizeof a);
//    req = 3;
	for (ll ii = 0;ii < min(100,n);ii ++){
        ll i = rng()%n;
        query(i);
        req = max(a[i].fi+a[i].se,req);
	}
	solve(0,n-1,0,req);
    return ans;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:58:25: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment [-Wclass-memaccess]
   58 |     memset(a,-1,sizeof a);
      |                         ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from prize.h:1,
                 from prize.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80