Submission #1112984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112984		SalihSahin	The Big Prize (IOI17_prize)	C++14	20 / 100	211 ms	12972 KiB

prize

#include <bits/stdc++.h>
#define pb push_back
#include "prize.h"

using namespace std;
/*
static const int max_q = 10000;
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;

vector<int> ask(int i) {
   query_count++;
   if(query_count > max_q) {
      cerr << "Query limit exceeded" << endl;
      //cout<<query_count<<" babag "<<endl;
      exit(0);
   }

   if(i < 0 || i >= n) {
      cerr << "Bad index: " << i << endl;
      exit(0);
   }

   vector<int> res(2);
   res[0] = rank_count[g[i] - 1][i + 1];
   res[1] = rank_count[g[i] - 1][n] - res[0];
   return res;
}
*/

const int MAXN = 2e5 + 5;
vector<vector<int> > check(MAXN, vector<int>(2, -1));
vector<int> small(MAXN);

void f(int n, int smallcnt, int l, int r, int cnt){
   if(l == r){
      small[l] = 1;
      return;
   }
   int mid = (l + r)/2;
   int m = -1;

   int k = rand() % 23;
   if(k >= 21){
      vector<int> delts;
      for(int i = l; i <= r; i++){
         delts.pb(i);
      } 
      random_shuffle(delts.begin(), delts.end());
      for(int i = 0; i < delts.size(); i++){
         if(check[delts[i]][0] == -1) check[delts[i]] = ask(delts[i]);
         if(check[delts[i]][0] + check[delts[i]][1] == smallcnt){
            m = delts[i];
            break;
         }
         else{
            small[delts[i]] = 1;
         }
      }
   }
   else{
      for(int delt = 0; delt <= (r - l + 1)/2 + 1; delt++){
         if(mid + delt <= r){
            if(check[mid + delt][0] == -1) check[mid + delt] = ask(mid + delt);
            if(check[mid + delt][0] + check[mid + delt][1] == smallcnt){
               m = mid + delt;
               break;
            }
            else{
               small[mid + delt] = 1;
            }
         }

         if(mid - delt >= l){
            if(check[mid - delt][0] == -1) check[mid - delt] = ask(mid - delt);
            if(check[mid - delt][0] + check[mid - delt][1] == smallcnt){
               m = mid - delt;
               break;
            }
            else{
               small[mid - delt] = 1;
            }
         }
      }
   }

   if(m == -1) return; // aralıktaki herkes small ve tagledik
   if(l > 0 && check[l-1][0] == -1) check[l-1] = ask(l-1);
   if(r < n-1 && check[r+1][0] == -1) check[r+1] = ask(r+1);

   int solcnt = check[m][0] - (l > 0 ? check[l-1][0] : 0);
   int sagcnt = check[m][1] - (r < n-1 ? check[r+1][1] : 0);
   if(l <= m-1 && solcnt > 0){
      //cout<<l<<" - "<<m-1<<" -> "<<solcnt<<endl;
      f(n, smallcnt, l, m-1, solcnt);
   }

   if(m+1 <= r && sagcnt > 0){
      //cout<<m+1<<" - "<<r<<" -> "<<sagcnt<<endl;
      f(n, smallcnt, m+1, r, sagcnt);
   }
}

long long kokbul(long long n){
   long long l = 1, r = n;
   while(l < r){
      long long m = (l + r)/2;

      if(m * m < n) l = m + 1;
      else r = m;
   }

   return l;
}

int find_best(int n) {
   int smallcnt = 0;
   int kok = kokbul(n) + 15;
   kok = min(kok, n);

   for(int i = 0; i < kok; i++){
      check[i] = ask(i);
      smallcnt = max(smallcnt, check[i][0] + check[i][1]);
   }
   for(int i = 0; i < kok; i++){
      if(check[i][0] + check[i][1] < smallcnt) small[i] = 1;
   }

   f(n, smallcnt, 0, n-1, smallcnt);
   int ans = -1;
   for(int i = 0; i < n; i++){
      if(small[i] == 1){
         if(check[i][0] == -1) check[i] = ask(i);
         if(check[i][0] + check[i][1] == 0){
            ans = i;
         }
      }
   }
   return ans;
}
/*
int main() {
   cin>>n;
   g.resize(n);

   for(int i = 0; i < n; i++) {
      cin>>g[i];
      if(g[i] < 1) {
         cerr << "Invalid rank " << g[i] << " at index " << i << endl;
         exit(0);
      }
   }

   int max_rank = *max_element(g.begin(), g.end());

   rank_count.resize(max_rank + 1, vector<int>(n + 1, 0));
   for(int r = 0; r <= max_rank; r++) {
      for(int i = 1; i <= n; i++) {
         rank_count[r][i] = rank_count[r][i - 1];
         if(g[i - 1] == r)
           rank_count[r][i]++;
      }
   }

   for(int i = 0; i <= n; i++)
      for(int r = 1; r <= max_rank; r++)
         rank_count[r][i] += rank_count[r - 1][i];

   int res = find_best(n);
   cout << res << endl << "Query count: " << query_count << endl;
   return 0;
}
*/
/*
int main() {
   mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
   int mx = 0;
   int t;
   cin>>t;
   while(t--){
      //cin>>n;
      //n = rng() % 55 + 7;
      n = 2e5 - rng() % 5000;
      g.resize(n);

      vector<int> cnts(3);
      cnts[0] = 1;
      cnts[1] = 3;
      cnts[2] = rng()%10 + 10;
      cnts[3] = rng()%20 + 400;
      cnts[4] = n - cnts[3] - cnts[2] - cnts[1] - cnts[0];

      for(int i = 0; i < n; i++){
         small[i] = 0;
         check[i][0] = check[i][1] = -1;
      }
      int ind = 0;
      for(int i = 0; i < n; i++){
         if(cnts[ind] == 0) ind++;
         g[i] = ind + 1;
         cnts[ind]--;
      }

      shuffle(g.begin(), g.end(), rng);

      for(int i = 0; i < n; i++) {
         if(g[i] < 1) {
            cerr << "Invalid rank " << g[i] << " at index " << i << endl;
            exit(0);
         }
      }

      int max_rank = *max_element(g.begin(), g.end());

      rank_count.clear();
      rank_count.resize(max_rank + 1, vector<int>(n + 1, 0));
      for(int r = 0; r <= max_rank; r++) {
         for(int i = 1; i <= n; i++) {
            rank_count[r][i] = rank_count[r][i - 1];
            if(g[i - 1] == r)
              rank_count[r][i]++;
         }
      }

      for(int i = 0; i <= n; i++)
         for(int r = 1; r <= max_rank; r++)
            rank_count[r][i] += rank_count[r - 1][i];

      int res = find_best(n);
      if(res == -1 || query_count > max_q){
         cout << res << endl << "Query count: " << query_count << endl;
      }
      mx = max(mx, query_count);
      query_count = 0;
   }
   cout<<mx<<endl;
   return 0;
}*/

Compilation message (stderr)

prize.cpp: In function 'void f(int, int, int, int, int)':
prize.cpp:52:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |       for(int i = 0; i < delts.size(); i++){
      |                      ~~^~~~~~~~~~~~~~

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