oj.uz

Submission #1113315

# Submission time Handle Problem Language Result Execution time Memory
1113315 2024-11-16T11:13:24 Z epicci23 The Big Prize (IOI17_prize) C++17
20 / 100
 172 ms 504 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 ask_all(int l,int r){
  for(int i=l;i<=r;i++){
    auto x = ask(i);
    if(x[0]+x[1]==0) return i;
  }
  return -23;
}

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 336 KB Output is correct
2 Correct 27 ms 336 KB Output is correct
3 Correct 19 ms 336 KB Output is correct
4 Correct 41 ms 336 KB Output is correct
5 Correct 20 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 25 ms 336 KB Output is correct
8 Correct 28 ms 336 KB Output is correct
9 Correct 25 ms 336 KB Output is correct
10 Correct 39 ms 336 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 504 KB Output is correct
2 Correct 25 ms 336 KB Output is correct
3 Correct 22 ms 336 KB Output is correct
4 Correct 41 ms 336 KB Output is correct
5 Correct 28 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 25 ms 336 KB Output is correct
8 Correct 23 ms 336 KB Output is correct
9 Correct 21 ms 336 KB Output is correct
10 Correct 39 ms 336 KB Output is correct
11 Incorrect 172 ms 336 KB Incorrect
12 Halted 0 ms 0 KB -