Advertisement
erek1e

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!
C++ 2.16 KB | None | 0 0
  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) {
  15.         vector<int> p = ask(i);
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement