oj.uz

Submission #946292

# Submission time Handle Problem Language Result Execution time Memory
946292 2024-03-14T13:25:08 Z jay_jayjay The Big Prize (IOI17_prize) C++17
0 / 100
 58 ms 768 KB 
// {{{1
extern "C" int __lsan_is_turned_off() { return 1; };
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>

#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 42
#endif
#define ll long long
#define all(x) (x).begin(),(x).end()

#define mod int(1e9+7)
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3f

void sleep(int x) { this_thread::sleep_for(chrono::seconds(x)); }
struct { template<typename T> operator T() { T x; cin>>x; return x; } } in;

struct __rng {
        mt19937_64 _rng;
        __rng() {
                ll ctime = chrono::high_resolution_clock::now().time_since_epoch().count();
                _rng = mt19937_64(ctime);
        }
        
        ll randint(ll l, ll h) {
                return uniform_int_distribution<int>(l,h)(_rng);
        }
} rng;
// 1}}}
#define rank rank2
// #define DBG

#define N 200000

vector<int> ask(int i);
#ifdef DBG

int n; vector<int> arr;
vector<int> ask(int i) {
        int l=0,r=0;
        for(int j=0;j<i;j++)if(arr[j]<arr[i]) l++;
        for(int j=i+1;j<n;j++)if(arr[j]<arr[i])r++;
        return vector<int>{l,r};
}
#endif
int ans[N][2];
int best=-1;


void ask2(int i) {
        if(best == i) return;
        
        if(ans[i][0]+ans[i][1] == 0) {
                auto x = ask(i);
                ans[i][0] = x[0];
                ans[i][1] = x[1];
                if(ans[i][0]+ans[i][1] == 0) best &= i;
        }
}

int rank(int i) {
        ask2(i);
        return ans[i][0]+ans[i][1];
}

int right(int i) {
        ask2(i);
        return ans[i][1];
}



// lower rank is more rare
void solve(int l, int r) {
        if(r<l) return;
        if(l==r) return void(rank(l));
        while(rank(l) != rank(r)) {
                while(rank(l) < rank(r)) l++;
                while(rank(l) > rank(r)) r--;
        }
        
        int m=(l+r)/2;
        solve(l,m);
        solve(m+1,r);
}

int find_best(int n) {
        solve(0, n-1);
        return best;
}

#ifdef DBG
int main() {
        n=in;arr.resize(n);for(auto&x:arr)x=in;
        
        int ans = find_best(n);
        printf("%d\n",ans);
        return arr[ans]!=1;
}
#endif

Compilation message

prize.cpp:22:73: warning: 'in' defined but not used [-Wunused-variable]
   22 | struct { template<typename T> operator T() { T x; cin>>x; return x; } } in;
      |                                                                         ^~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 516 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 768 KB Incorrect
2 Halted 0 ms 0 KB -