oj.uz

Submission #1113353

# Submission time Handle Problem Language Result Execution time Memory
1113353 2024-11-16T12:19:52 Z epicci23 The Big Prize (IOI17_prize) C++17
20 / 100
 202 ms 1892 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 = 10;

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;
  int BL = (int)sqrtl(r-l+1);
  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 lf = Learn(l,l+BL-1);
  if(lf!=-1) return lf;
  if(u[1]==suf) Cache=u;
  else suf--;
  return Learn(l+BL+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 11 ms 336 KB Output is correct
2 Correct 16 ms 592 KB Output is correct
3 Correct 14 ms 592 KB Output is correct
4 Correct 10 ms 336 KB Output is correct
5 Correct 15 ms 592 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 17 ms 512 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 15 ms 336 KB Output is correct
10 Correct 27 ms 656 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 336 KB Output is correct
2 Correct 15 ms 848 KB Output is correct
3 Correct 16 ms 592 KB Output is correct
4 Correct 9 ms 336 KB Output is correct
5 Correct 15 ms 592 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 14 ms 592 KB Output is correct
8 Correct 15 ms 724 KB Output is correct
9 Correct 14 ms 592 KB Output is correct
10 Correct 23 ms 1312 KB Output is correct
11 Correct 19 ms 592 KB Output is correct
12 Correct 10 ms 336 KB Output is correct
13 Correct 30 ms 584 KB Output is correct
14 Correct 13 ms 708 KB Output is correct
15 Correct 29 ms 592 KB Output is correct
16 Partially correct 150 ms 1752 KB Partially correct - number of queries: 7678
17 Correct 7 ms 336 KB Output is correct
18 Partially correct 159 ms 1748 KB Partially correct - number of queries: 8924
19 Correct 8 ms 336 KB Output is correct
20 Correct 53 ms 744 KB Output is correct
21 Correct 61 ms 932 KB Output is correct
22 Correct 19 ms 336 KB Output is correct
23 Correct 11 ms 592 KB Output is correct
24 Correct 8 ms 592 KB Output is correct
25 Correct 81 ms 1008 KB Output is correct
26 Correct 79 ms 1256 KB Output is correct
27 Correct 12 ms 744 KB Output is correct
28 Partially correct 146 ms 1892 KB Partially correct - number of queries: 7455
29 Partially correct 114 ms 1596 KB Partially correct - number of queries: 6016
30 Partially correct 202 ms 1532 KB Partially correct - number of queries: 9239
31 Correct 10 ms 336 KB Output is correct
32 Correct 25 ms 820 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 53 ms 912 KB Output is correct
35 Correct 19 ms 772 KB Output is correct
36 Correct 51 ms 944 KB Output is correct
37 Correct 15 ms 756 KB Output is correct
38 Correct 11 ms 740 KB Output is correct
39 Correct 98 ms 1432 KB Output is correct
40 Partially correct 141 ms 1504 KB Partially correct - number of queries: 7873
41 Partially correct 113 ms 996 KB Partially correct - number of queries: 5736
42 Partially correct 113 ms 1172 KB Partially correct - number of queries: 5736
43 Partially correct 95 ms 1820 KB Partially correct - number of queries: 5454
44 Correct 72 ms 720 KB Output is correct
45 Correct 53 ms 840 KB Output is correct
46 Correct 8 ms 336 KB Output is correct
47 Correct 68 ms 1808 KB Output is correct
48 Partially correct 125 ms 1484 KB Partially correct - number of queries: 6771
49 Correct 19 ms 336 KB Output is correct
50 Partially correct 170 ms 1744 KB Partially correct - number of queries: 8907
51 Correct 74 ms 1172 KB Output is correct
52 Correct 12 ms 736 KB Output is correct
53 Correct 21 ms 608 KB Output is correct
54 Correct 84 ms 1672 KB Output is correct
55 Correct 8 ms 336 KB Output is correct
56 Partially correct 194 ms 1428 KB Partially correct - number of queries: 8975
57 Partially correct 131 ms 1408 KB Partially correct - number of queries: 6858
58 Partially correct 116 ms 1424 KB Partially correct - number of queries: 6538
59 Partially correct 104 ms 1180 KB Partially correct - number of queries: 5735
60 Partially correct 95 ms 1436 KB Partially correct - number of queries: 5486
61 Correct 17 ms 592 KB Output is correct
62 Correct 9 ms 336 KB Output is correct
63 Correct 20 ms 584 KB Output is correct
64 Correct 18 ms 744 KB Output is correct
65 Correct 19 ms 584 KB Output is correct
66 Correct 36 ms 848 KB Output is correct
67 Correct 23 ms 956 KB Output is correct
68 Correct 8 ms 592 KB Output is correct
69 Correct 36 ms 916 KB Output is correct
70 Correct 25 ms 932 KB Output is correct
71 Incorrect 187 ms 1520 KB Incorrect
72 Halted 0 ms 0 KB -