Submission #1015935

#TimeUsernameProblemLanguageResultExecution timeMemory
1015935hotboy2703The Big Prize (IOI17_prize)C++17
0 / 100
1 ms3416 KiB
#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); } int find_best(int n) { memset(a,-1,sizeof a); req = 3; // for (ll i = 0;i < min(500,n);i ++){ // 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:57: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]
   57 |     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
      |            ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...