IOI problem 2 partial solution

Here is code that gave 65/100 points :)

1. include "overtaking.h"
2. include <bits/stdc++.h>
3. include <random>

using namespace std; typedef long long ll; typedef vector<ll> vll; typedef pair<ll, ll> pll;

void print(vll O) {

   for(auto tt : O) cerr << tt << ' ';
   cerr << endl;

}

ll l, n, x, m, nt; ll Pace[1000], SP[1000], DT[1000], RAT[1000]; ll DP[1000][1000], ST[1000][2048], OT[1000][1000]; pll TT[1000];

ll cm(int i) {

   auto itr = lower_bound(OT[i-1], OT[i-1]+n, RAT[i-1]);
   if(itr == OT[i-1]) return -1;
   itr--; ll tst = itr-OT[i-1];
   ll l = nt, r = nt+tst, ans = -1;
   while(l <= r) {
       if(l%2 == 1) ans = max(ans, ST[i][l++]);
       if(r%2 == 0) ans = max(ans, ST[i][r--]);
       l /= 2, r /= 2;
   }
   return ans;

}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {

   l = L, n = N, x = X, m = M;
   vector<int> RR; for(int i = 0; i < n; i++) RR.push_back(i);
   random_shuffle(RR.begin(), RR.end());
   for(int i = 0; i < n; i++) {
       Pace[i] = W[RR[i]];
       DT[i] = T[RR[i]];
   }
   for(int i = 0; i < m; i++) SP[i] = S[i];

   set<array<ll, 3>> TAT;
   for(int i = 0; i < n; i++) {
       TAT.insert({DT[i], Pace[i], i});
       DP[0][i] = DT[i];
   }

   for(int i = 1; i < m; i++) {
       ll mx = -1;
       for(int j = 0; j < n; j++) {
           auto itr = TAT.begin();
           ll idx = (*itr)[2];
           TAT.erase(itr);
           mx = max(mx, DP[i-1][idx]+Pace[idx]*(SP[i]-SP[i-1]));
           DP[i][idx] = mx;
       }
       for(int j = 0; j < n; j++)
           TAT.insert({DP[i][j], Pace[j], j});
   }

   nt = 1<<int(ceil(log2(n)));
   for(int i = 1; i < m; i++) {
       for(int j = 0; j < n; j++) TT[j] = {DP[i-1][j], DP[i][j]};
       sort(TT, TT+n);
       for(int j = 0; j < n; j++) OT[i-1][j] = TT[j].first;
       for(int j = nt; j < nt+n; j++) ST[i][j] = TT[j-nt].second;
       for(int j = nt-1; j > 0; j--) ST[i][j] = max(ST[i][2*j], ST[i][2*j+1]);
   }

}

long long arrival_time(long long Y) {

   RAT[0] = Y;
   for(int i = 1; i < m; i++)
       RAT[i] = max(cm(i), RAT[i-1]+x*(SP[i]-SP[i-1]));
   return RAT[m-1];

}

n, k = map(int, input().split()) if k > 336: print("Your wish is granted!") elif 2**k >= n: print("Your wish is granted!") else: print("You will become a flying monkey!")

References

This article "IOI problem 2 partial solution" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:IOI problem 2 partial solution. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---