oj.uz

Submission #1113540

# Submission time Handle Problem Language Result Execution time Memory
1113540 2024-11-16T17:44:00 Z epicci23 The Big Prize (IOI17_prize) C++17
20 / 100
 22 ms 980 KB 
#include "bits/stdc++.h"
#include "prize.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int rand(int l,int r){
  return l + rng() % (r-l+1);
}


const int BL = 500;

int suf = -1;
vector<int> Cache={-1,-1};
map<int,vector<int>> dp;
 
vector<int> Ask(int i){
  if( dp.count(i) ) return dp[i];
  return dp[i] = ask(i);
}
 
int ask_all(int l,int r){
  for(int i = l; i <= r; i++){
    vector<int> x = Ask(i);
    if(x[0] + x[1] == 0) return i;
    if(x[1] == suf) Cache = x;
    else suf--;
  }
  return -23;
}
 
int Learn(int l,int r){
  if(l>r) return -1;
  if(l==r){
    auto u = Ask(l);
    if(u[0] + u[1] == 0) return l;
    if(u[1] == suf) Cache=u;
    else suf--;
    return -1;
  }

  auto X = Ask(r);
  if(X[0] + X[1] == 0) return r;
  if(X[1] == suf) return -1;

  if(l+BL+1<r){
    auto u = Ask(l + BL);
    if(u[0]+u[1]==0) return l+BL;
    if(u[1] == suf) return Learn(l+BL+1,r-1);
    int hm = Learn(l,l+BL-1);
    if(hm != -1) return hm;
    if(u[1] == suf) Cache = u;
    else suf--;
    if(X[1] == suf - ( Cache[0] + Cache[1] > X[0] + X[1] ) ) return -1;
    int hm2 = Learn(l+BL+1,r-1);
    if(hm2 != -1) return hm;
    if(X[1] == suf) Cache = X;
    else suf--;
    return -1;
  }

  int mid = (l+r)/2;
  auto u = Ask(mid);
  if(u[0] + u[1] == 0) return mid;
  if(u[1] == suf) return Learn(mid + 1,r - 1);
  int lf = Learn(l,mid - 1);
  if(lf != -1) return lf;
  if(u[1]==suf) Cache = u;
  else suf--; 
  if(X[1] == suf - ( Cache[0] + Cache[1] > X[0] + X[1] ) ) return -1;
  int hm = Learn( mid + 1, r - 1 );
  if(hm != -1) return hm;
  if(X[1] == suf) Cache = X;
  else suf--;
  return -1;
}
 
int find_best(int n){
  if(n <= 1000) return ask_all(0, n - 1);
  int art = 0;
  for(int i = 0; i <= 500; i++){
  	if(art == 5) return Learn(i, n - 1);
    vector<int> x = Ask(i);
    if(x[0] + x[1] == 0) return i;
    if(x[0] + x[1] > Cache[0] + Cache[1]) art++;
    if(x[0] + x[1] >= Cache[0] + Cache[1]){
      Cache = x;
      suf = Cache[1];
    }
    else suf--;
  }
  return Learn(501, n - 1 );
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 592 KB Output is correct
2 Correct 17 ms 592 KB Output is correct
3 Correct 17 ms 592 KB Output is correct
4 Correct 8 ms 336 KB Output is correct
5 Correct 15 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 13 ms 524 KB Output is correct
8 Correct 14 ms 336 KB Output is correct
9 Correct 22 ms 848 KB Output is correct
10 Correct 22 ms 752 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 336 KB Output is correct
2 Correct 16 ms 840 KB Output is correct
3 Correct 15 ms 592 KB Output is correct
4 Correct 10 ms 336 KB Output is correct
5 Correct 18 ms 980 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 15 ms 504 KB Output is correct
8 Correct 18 ms 716 KB Output is correct
9 Correct 14 ms 336 KB Output is correct
10 Correct 20 ms 720 KB Output is correct
11 Incorrect 18 ms 592 KB Integer -1 violates the range [0, 199999]
12 Halted 0 ms 0 KB -