oj.uz

Submission #1113348

# Submission time Handle Problem Language Result Execution time Memory
1113348 2024-11-16T12:13:03 Z epicci23 The Big Prize (IOI17_prize) C++17
20 / 100
 194 ms 1600 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;

const int S = 100;
const int S2 = 20;

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

int find_best(int n){
  if(n<=1000) return ask_all(0,n-1);
  for(int i=0;i<=500;i++){
    vector<int> x = Ask(i);
    if(x[0]+x[1]==0) return i;
    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 9 ms 592 KB Output is correct
2 Correct 9 ms 592 KB Output is correct
3 Correct 9 ms 336 KB Output is correct
4 Correct 10 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 9 ms 336 KB Output is correct
8 Correct 8 ms 592 KB Output is correct
9 Correct 8 ms 336 KB Output is correct
10 Correct 9 ms 476 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 336 KB Output is correct
2 Correct 10 ms 440 KB Output is correct
3 Correct 9 ms 592 KB Output is correct
4 Correct 8 ms 508 KB Output is correct
5 Correct 9 ms 720 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 11 ms 336 KB Output is correct
8 Correct 9 ms 704 KB Output is correct
9 Correct 11 ms 592 KB Output is correct
10 Correct 11 ms 336 KB Output is correct
11 Correct 25 ms 516 KB Output is correct
12 Correct 12 ms 336 KB Output is correct
13 Correct 46 ms 476 KB Output is correct
14 Correct 17 ms 520 KB Output is correct
15 Correct 38 ms 1056 KB Output is correct
16 Incorrect 194 ms 1600 KB Incorrect
17 Halted 0 ms 0 KB -