| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 390557 | mehrdad_sohrabi | The Big Prize (IOI17_prize) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=2e5+100;
/*
static const int max_q = 10000;
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;
vector<int32_t> ask(int i) {
query_count++;
if(query_count > max_q) {
cerr << "Query limit exceeded" << endl;
exit(0);
}
if(i < 0 || i >= n) {
cerr << "Bad index: " << i << endl;
exit(0);
}
vector<int32_t> res(2);
res[0] = rank_count[g[i] - 1][i + 1];
res[1] = rank_count[g[i] - 1][n] - res[0];
return res;
}
*/
ll fen[N];
void add(ll idx,ll val){
for (;idx<N;idx+=idx & -(idx)){
fen[idx]+=val;
}
}
ll get(ll idx){
ll s=0;
for (;idx;idx-=idx & (-idx)){
s+=fen[idx];
}
return s;
}
ll val[N];
pii a[N];
ll mx=0;
pii ASK(int i){
if (val[i]==-1){
vector <int32_t> ans=ask(i);
a[i]={ans[0],ans[1]};
val[i]=a[i].F+a[i].S;
}
return a[i];
}
ll vis[N];
ll aaa=-1;
void solve(ll l,ll r,ll kl,ll kr){
if (kl+kr+(get(r)-get(l))>=mx || aaa!=-1) return ;
vector <int> cand;
for (int i=l;i<r;i++){
if (vis[i]){
cout << 1/0;
}
cand.pb(i);
}
ll s=cand.size();
s/=2;
if (cand.size()==0) return ;
if (cand.size()==1){
ASK(cand[0]);
if (val[cand[0]]<mx){
vis[cand[0]]=1;
}
// if (val[cand[0]]>mx) cout << 1/0;
return ;
}
ll mid=cand[s-1]+1;
ll p1=0,p2=0;
for (int i=s;i<cand.size();i++){
if (aaa!=-1) return ;
ASK(cand[i]);
if (val[cand[i]]<mx){
vis[cand[i]]=1;
if (val[cand[i]]==0) aaa=cand[i];
if (a[cand[i]].F==0) p1=0;
if (a[cand[i]].S==0) p2=0;
continue;
}
if (val[cand[i]]>mx) cout << 1/0;
if (i!=cand.size()-1 && p1==0){
solve(cand[i+1],r,a[cand[i]].F,kr);
}
if (p2==0)
solve(l,mid,kl,a[cand[i]].S+i-s);
return ;
}
if (aaa!=-1 || p1==1) return ;
solve(l,mid,kl,kr+cand.size()-s);
}
int32_t find_best(int32_t n) {
memset(val,-1,sizeof val);
vector <int> rnd;
for (int i=0;i<n;i++){
rnd.pb(i);
}
random_shuffle(rnd.begin(),rnd.end());
/*
if (n>1000){
ll s=0;
ll K=500;
for (int i=s;i<s+K;i++){
ASK(i);
mx=max(mx,val[i]);
if (val[i]==0) return i;
}
ll tt=0;
for (int i=0;i<K;i++){
if (val[i]!=mx) tt++;
}
solve(K,n,tt,0);
}
else{
*/
ll kk=448;
for (int i=0;i<min(n,kk);i++){
ASK(rnd[i]);
mx=max(mx,val[rnd[i]]);
if (val[rnd[i]]==0) return rnd[i];
if (val[rnd[i]]>22){
kk=i+1;
break;
}
}
for (int i=0;i<min(n,kk);i++){
if (val[rnd[i]]!=mx){
add(rnd[i]+1,1);
}
}
solve(0,n,0,0);
for (int i=0;i<n;i++){
if (vis[i]==1 && val[i]==0) return i;
}
return 0;
}
/*
int32_t main() {
cin >> n;
g.resize(n);
for(int i = 0; i < n; i++) {
//cin >> g[i];
g[i]=2;
if(g[i] < 1) {
cerr << "Invalid rank " << g[i] << " at index " << i << endl;
exit(0);
}
}
ll z=rand()%n;
g[z]=1;
cout << z << endl;
int max_rank = *max_element(g.begin(), g.end());
rank_count.resize(max_rank + 1, vector<int>(n + 1, 0));
for(int r = 0; r <= max_rank; r++) {
for(int i = 1; i <= n; i++) {
rank_count[r][i] = rank_count[r][i - 1];
if(g[i - 1] == r)
rank_count[r][i]++;
}
}
for(int i = 0; i <= n; i++)
for(int r = 1; r <= max_rank; r++)
rank_count[r][i] += rank_count[r - 1][i];
int res = find_best(n);
cout << res << endl << "Query count: " << query_count << endl;
return 0;
}
*/
/*
8
3 2 3 1 3 3 2 3
*/