Submission #407007

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
407007	2021-05-18 10:17:26	ja_kingy	The Big Prize (IOI17_prize)	C++14	100 / 100	74 ms	6060 KiB

prize

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "prize.h"
#include <iostream>
using namespace std;
vector<int> cache[200000];
int ans, cnt, done[200000], n;
vector<int> askc(int x) {
  if (!done[x]) {
    done[x] = 1;
    cache[x] = ask(x);
  }
  return cache[x];
}
void find(int l, int r, int el, int er) {
  if (r < l) return;
  if (cnt == el + er) return;
  int m = l+r>>1;
  int x = m;
  vector<int> res;
  for (; x <= r; x++) {
    res = askc(x);
    if (res[0] == 0 && res[1] == 0) ans = x;
    if (res[0] + res[1] > cnt) {
      cnt = res[0] + res[1];
      find(0, n-1, 0, 0);
    }
    if (res[0] + res[1] == cnt) break;
  }
  if (l != r) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

prize.cpp: In function 'void find(int, int, int, int)':
prize.cpp:18:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |  int m = l+r>>1;
      |          ~^~

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80