//
// ~oisín~ C++ Template
//
#include <bits/stdc++.h>
#define MX_N 200005
#define mp make_pair
#define mod7 1000000007
#define modpi 314159
#define PI 3.141592653589793238
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a) a.begin(),a.end()
#define fi first
#define se second
#define ll long long int
#define ull unsigned long long int
#include "prize.h"
int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] = {+0, +0, +1, -1};
int dy4[4] = {+1, -1, +0, +0};
ll gcd(ull a, ull b){
return (a==0)?b:gcd(b%a,a);
}
ll lcm(ull a, ull b){
return a*(b/gcd(a,b));
}
const long long INF = 1e18;
using namespace std;
int tipe[MX_N];
int N;
bitset<MX_N> in_cache;
pair<int, int> cache[MX_N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//vector<int> ask(int i){
// vector<int> res = {0, 0};
// for(int j=i+1;j<N;++j){
// res[1] += (tipe[j] < tipe[i]);
// }
// for(int j=0;j<i;++j){
// res[0] += (tipe[j] < tipe[i]);
// }
// return res;
//}
pair<int, int> query(int i){
if(!in_cache[i]){
auto res = ask(i);
cache[i].fi = res[0];
cache[i].se = res[1];
}
in_cache[i] = 1;
return cache[i];
}
set<int> pos[MX_N];
int find_best(int n){
uniform_int_distribution<> Id(0, n-1);
in_cache.set();
in_cache.flip();
if(n <= 50){
for(int i=0;i<n;++i){
auto [L, R] = query(i);
if(L == 0 && R == 0){
return i;
}
}
}
int best = 1000000009;
set<int> candidates;
while(candidates.size() < 50){
int i = Id(rng);
auto [L, R] = query(i);
if(L == 0 && R == 0){
return i;
}
candidates.insert(i);
pos[L+R].insert(i);
if(pos[L+R].size() >= 2){
best = min(best, L+R);
}
}
while(best != 0){
vector<pair<double, pair<int, int> > > options;
int last = -1;
for(int i : pos[best]){
double rho = 0.0;
if(i == 0){
rho = 0.0;
last = i;
continue;
}
if(last == -1){
rho += (double)query(i).fi;
rho /= (double)i;
options.pb(make_pair(rho, make_pair(last, i)));
last = i;
continue;
}
if(last+1 == i){
rho = 0.0;
last = i;
continue;
}
rho += (double)(query(i).fi - query(last).fi);
rho /= (double)(i-last-1);
options.pb(make_pair(rho, make_pair(last, i)));
last = i;
}
if(last+1 != n){
double rho = 0.0;
rho += (double)query(last).se;
rho /= (double)(n-last-1);
options.pb(make_pair(rho, make_pair(last, n)));
}
sort(All(options));
reverse(All(options));
bool best_update = false;
for(auto pp : options){
if(best_update){
break;
}
int lo = pp.se.fi;
int hi = pp.se.se;
int in_range;
if(lo == -1){
in_range = query(hi).fi;
}else if(hi == n){
in_range = query(lo).se;
}else{
in_range = query(hi).fi - query(lo).fi;
}
while(in_range > 0){
int r = hi - lo - 1;
int i = lo + 1 + (Id(rng)%r);
auto [L, R] = query(i);
if(L == 0 && R == 0){
return i;
}
if(L+R == best){
double rhoL = 0.0, rhoR = 0.0;
if(lo == -1){
if(i == 0){
rhoL = 0.0;
}else{
rhoL = L;
rhoL /= (double)(i);
}
}else{
if(lo+1 == i){
rhoL = 0.0;
}else{
rhoL = L - query(lo).fi;
rhoL /= (double)(i-lo-1);
}
}
if(hi == n){
if(i == n-1){
rhoR = 0.0;
}else{
rhoR = R;
rhoR /= (double)(n-i-1);
}
}else{
if(i+1 == hi){
rhoR = 0.0;
}else{
rhoR = query(hi).fi - L;
rhoR /= (double)(hi-i-1);
}
}
if(rhoR > rhoL){
lo = i;
}else{
hi = i;
}
}else if(L+R < best){
pos[L+R].insert(i);
in_range--;
if(pos[L+R].size() >= 2){
best = L+R;
best_update = true;
break;
}
}
}
}
}
}
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:84:14: warning: control reaches end of non-void function [-Wreturn-type]
84 | set<int> candidates;
| ^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9792 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9804 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9964 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9800 KB |
Output is correct |
| 5 |
Correct |
9 ms |
9812 KB |
Output is correct |
| 6 |
Correct |
8 ms |
9800 KB |
Output is correct |
| 7 |
Correct |
7 ms |
9980 KB |
Output is correct |
| 8 |
Correct |
7 ms |
9820 KB |
Output is correct |
| 9 |
Correct |
7 ms |
9928 KB |
Output is correct |
| 10 |
Correct |
9 ms |
9860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9920 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9816 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9852 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9840 KB |
Output is correct |
| 5 |
Correct |
7 ms |
9800 KB |
Output is correct |
| 6 |
Correct |
7 ms |
9968 KB |
Output is correct |
| 7 |
Correct |
7 ms |
9832 KB |
Output is correct |
| 8 |
Correct |
9 ms |
9920 KB |
Output is correct |
| 9 |
Correct |
7 ms |
9848 KB |
Output is correct |
| 10 |
Correct |
8 ms |
9864 KB |
Output is correct |
| 11 |
Correct |
24 ms |
10264 KB |
Output is correct |
| 12 |
Incorrect |
119 ms |
10824 KB |
Incorrect |
| 13 |
Halted |
0 ms |
0 KB |
- |
