oj.uz

Submission #1113535

# Submission time Handle Problem Language Result Execution time Memory
1113535 2024-11-16T17:40:21 Z epicci23 The Big Prize (IOI17_prize) C++17
20 / 100
 179 ms 2504 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 = 100000;

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<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);
    int hm = Learn(l,l+BL-1);
    if(hm != -1) return hm;
    if(u[1] == suf) Cache = u;
    else suf--;
    return Learn(l+BL+1,r);
  }

  int mid = rand(l , r);
  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 12 ms 336 KB Output is correct
3 Correct 12 ms 336 KB Output is correct
4 Correct 8 ms 336 KB Output is correct
5 Correct 9 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 10 ms 336 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 10 ms 476 KB Output is correct
10 Correct 11 ms 336 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 584 KB Output is correct
2 Correct 10 ms 704 KB Output is correct
3 Correct 10 ms 700 KB Output is correct
4 Correct 9 ms 336 KB Output is correct
5 Correct 10 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 9 ms 336 KB Output is correct
8 Correct 10 ms 336 KB Output is correct
9 Correct 10 ms 972 KB Output is correct
10 Correct 13 ms 336 KB Output is correct
11 Correct 18 ms 592 KB Output is correct
12 Correct 10 ms 496 KB Output is correct
13 Incorrect 179 ms 2504 KB Incorrect
14 Halted 0 ms 0 KB -