oj.uz

Submission #72824

# Submission time Handle Problem Language Result Execution time Memory
72824 2018-08-27T03:47:48 Z funcsr The Big Prize (IOI17_prize) C++17
20 / 100
 75 ms 2212 KB 
#include "prize.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cassert>
#include <random>
using namespace std;
#define rep(i,n)for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
typedef pair<int, int> P;
mt19937 mt_rand(114514);
int mp = 0;
P cache[200000];
int Q=0;
P query(int x) {
  if (cache[x] != P(-1, -1)) return cache[x];
  Q++;
  assert(Q<=10000);
  //if(Q%100==0)cout<<"Q="<<Q<<"\n";
  vector<int> ret = ask(x);
  return cache[x] = {ret[0], ret[1]};
}

int solve(int l, int r, int num, int left) {
  assert(num >= 0 && left >= 0);
  if (num == 0) return -1;
  //cout<<"solve("<<l<<","<<r<<", num="<<num<<")\n";
  //int mm = (l+r)/2;
  int mm = l+(mt_rand()%(r-l+1));
  for (int mid=mm+1; mid<=r; mid++) {
    P ret = query(mid);
    if (ret._1+ret._2 == 0) return mid;
    if (ret._1+ret._2 != mp) continue;
    if (mid > l) {
      int o = solve(l, mid-1, ret._1-left, left);
      if (o != -1) return o;
    }
    if (mid < r) {
      int o = solve(mid+1, r, num-(ret._1-left), ret._1);
      if (o != -1) return o;
    }
    return -1;
  }
  for (int mid=mm; mid>=l; mid--) {
    P ret = query(mid);
    if (ret._1+ret._2 == 0) return mid;
    if (ret._1+ret._2 != mp) continue;
    if (mid > l) {
      int o = solve(l, mid-1, ret._1-left, left);
      if (o != -1) return o;
    }
    if (mid < r) {
      int o = solve(mid+1, r, num-(ret._1-left), ret._1);
      if (o != -1) return o;
    }
    return -1;
  }
  return -1;
}

int find_best(int N) {
  if (N <= 5000) {
    rep(i, N) {
      P ret = query(i);
      if (ret._1+ret._2 == 0) return i;
    }
    abort();
  }
  rep(i, N) cache[i] = P(-1, -1);
  rep(i, 30) {
    P ret = query(mt_rand()%N);
    mp = max(mp, ret._1+ret._2);
  }
  //cout<<"mp="<<mp<<"\n";
  assert(mp < 500);
  int r = solve(0, N-1, mp, 0);
  assert(r != -1);
  return r;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1784 KB Output is correct
2 Correct 6 ms 1972 KB Output is correct
3 Correct 4 ms 1972 KB Output is correct
4 Correct 5 ms 1972 KB Output is correct
5 Correct 4 ms 2000 KB Output is correct
6 Correct 6 ms 2004 KB Output is correct
7 Correct 4 ms 2200 KB Output is correct
8 Correct 5 ms 2200 KB Output is correct
9 Correct 4 ms 2200 KB Output is correct
10 Correct 6 ms 2212 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2212 KB Output is correct
2 Correct 5 ms 2212 KB Output is correct
3 Correct 5 ms 2212 KB Output is correct
4 Correct 5 ms 2212 KB Output is correct
5 Correct 6 ms 2212 KB Output is correct
6 Correct 5 ms 2212 KB Output is correct
7 Correct 7 ms 2212 KB Output is correct
8 Correct 5 ms 2212 KB Output is correct
9 Correct 4 ms 2212 KB Output is correct
10 Correct 5 ms 2212 KB Output is correct
11 Correct 7 ms 2212 KB Output is correct
12 Correct 6 ms 2212 KB Output is correct
13 Correct 11 ms 2212 KB Output is correct
14 Correct 6 ms 2212 KB Output is correct
15 Correct 15 ms 2212 KB Output is correct
16 Correct 50 ms 2212 KB Output is correct
17 Correct 5 ms 2212 KB Output is correct
18 Partially correct 75 ms 2212 KB Partially correct - number of queries: 5947
19 Correct 5 ms 2212 KB Output is correct
20 Correct 21 ms 2212 KB Output is correct
21 Correct 32 ms 2212 KB Output is correct
22 Correct 9 ms 2212 KB Output is correct
23 Correct 5 ms 2212 KB Output is correct
24 Correct 5 ms 2212 KB Output is correct
25 Correct 22 ms 2212 KB Output is correct
26 Correct 35 ms 2212 KB Output is correct
27 Correct 5 ms 2212 KB Output is correct
28 Partially correct 42 ms 2212 KB Partially correct - number of queries: 5117
29 Correct 42 ms 2212 KB Output is correct
30 Partially correct 34 ms 2212 KB Partially correct - number of queries: 5932
31 Correct 5 ms 2212 KB Output is correct
32 Correct 6 ms 2212 KB Output is correct
33 Incorrect 2 ms 2212 KB answer is not correct
34 Halted 0 ms 0 KB -