# IOI '17 P4 - The Big Prize

Jun 16th, 2022
681
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. #include <set>
5. #include <cassert>
6. #include "prize.h"
7.
8. using namespace std;
9.
10. vector<int> l, r;
11. set<int> q; // queried indices that were not expensive
12. int expensiveCnt = 0;
13. void query(int i) {
14.     if (l[i] == -1) {
16.         l[i] = p[0], r[i] = p[1];
17.         if (l[i] + r[i] == expensiveCnt) q.insert(i); // if not expensive
18.     }
19. }
20.
21. bool isExpensive(int i) {
22.     if (l[i] == -1) query(i);
23.     return l[i] + r[i] < expensiveCnt;
24. }
25. bool isDiamond(int i) {
26.     return l[i] + r[i] == 0;
27. }
28.
29. int diamond = -1;
30. void divideAndConquer(int left, int right, int k, int lBefore = 0, int rAfter = 0) { // k is how many expensives in this range
31.     if (!k || diamond != -1) return;
32.
33.     set<int>::iterator it = q.lower_bound(left);
34.     if (it != q.end() && *it <= right) {
35.         int mid = *it;
36.         divideAndConquer(left, mid-1, l[mid]-lBefore, lBefore, r[mid]);
37.         divideAndConquer(mid+1, right, r[mid]-rAfter, l[mid], rAfter);
38.         return;
39.     }
40.
41.     int mid = (left + right) / 2, startMid = mid;
42.     bool reachedLeft = false;
43.     while (isExpensive(mid)) {
44.         if (isDiamond(mid)) {
45.             diamond = mid;
46.             return;
47.         }
48.         if (!reachedLeft) {
49.             --mid;
50.             if (mid < left) reachedLeft = true, mid = startMid;
51.         }
52.         if (reachedLeft) {
53.             ++mid;
54.             if (mid > right) {
55.                 assert(k == right-left+1);
56.                 return;
57.             }
58.         }
59.     }
60.
61.     assert(!isExpensive(mid));
62.     if (!reachedLeft) divideAndConquer(left, mid-1, l[mid]-lBefore, lBefore, r[mid]);
63.     divideAndConquer(mid+1, right, r[mid]-rAfter, l[mid], rAfter);
64. }
65.
66. int find_best(int n){
67.     l = r = vector<int>(n, -1);
68.     // we will call all objects that are not the cheapest objects expensive
69.     int maxExpensive = min(3, n), startQ = min(maxExpensive+1, n);
70.     for (int i = 0; i < startQ; ++i) {
71.         query(i);
72.         if (isDiamond(i)) return i;
73.         expensiveCnt = max(expensiveCnt, l[i]+r[i]);
74.     }
75.
76.     divideAndConquer(0, n-1, expensiveCnt);
77.     return diamond;
78. }