oj.uz

Submission #1113337

# Submission time Handle Problem Language Result Execution time Memory
1113337 2024-11-16T11:59:35 Z epicci23 The Big Prize (IOI17_prize) C++17
20 / 100
 195 ms 1740 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 L = -1 , suf = -1;
vector<int> Cache;
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){
    auto u = Ask(l);
    if(u[0]+u[1]==0) return l;
    if(u[0]+u[1]==Cache[0]+Cache[1]) Cache=u;
    return -1;
  }
  if()
  int BL = (int)sqrtl(r-l+1);
  auto x = ask(l+BL-1);
  
}*/

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(L==-1) Cache=x;
    else if(x[0]+x[1]>=Cache[0]+Cache[1]) Cache=x;
  }
  suf=Cache[1];
  L=500;
  while(L+S<n){
    vector<int> x = Ask(L+S);
    if(x[0]+x[1]==0) return L+S;
    if(suf==x[1]){
      L+=S;
      Cache=x;
      continue;
    }
    int p = L;
    while(p+S2<L+S){
      p+=S2;
      vector<int> u = Ask(p);
      if(u[0]+u[1]==0) return p;
      if(suf==u[1]) Cache=u;
      else{
        int xd = ask_all(p-S2,p);
        if(xd!=-23) return xd;
      }
    }
    int xd = ask_all(p,L+S);
    if(xd!=-23) return xd;
    L+=S;
  }
  return ask_all(L,n-1);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 592 KB Output is correct
2 Correct 34 ms 1236 KB Output is correct
3 Correct 26 ms 628 KB Output is correct
4 Correct 40 ms 1592 KB Output is correct
5 Correct 24 ms 592 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 24 ms 584 KB Output is correct
8 Correct 23 ms 716 KB Output is correct
9 Correct 27 ms 748 KB Output is correct
10 Correct 44 ms 976 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 636 KB Output is correct
2 Correct 25 ms 584 KB Output is correct
3 Correct 29 ms 1016 KB Output is correct
4 Correct 44 ms 840 KB Output is correct
5 Correct 23 ms 760 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 28 ms 1292 KB Output is correct
8 Correct 26 ms 556 KB Output is correct
9 Correct 25 ms 768 KB Output is correct
10 Correct 46 ms 792 KB Output is correct
11 Correct 25 ms 584 KB Output is correct
12 Correct 11 ms 336 KB Output is correct
13 Correct 58 ms 1248 KB Output is correct
14 Correct 18 ms 336 KB Output is correct
15 Correct 46 ms 1740 KB Output is correct
16 Incorrect 195 ms 1652 KB Incorrect
17 Halted 0 ms 0 KB -