oj.uz

Submission #1112958

# Submission time Handle Problem Language Result Execution time Memory
1112958 2024-11-15T10:03:48 Z SalihSahin The Big Prize (IOI17_prize) C++14
0 / 100
 186 ms 12176 KB 
#include <bits/stdc++.h>
#define pb push_back
#include "prize.h"

using namespace std;

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;

   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);
   }
}

int kokbul(int n){
   int l = 1, r = n;
   while(l < r){
      int 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) + 3;
   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;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 177 ms 12112 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 186 ms 12176 KB Incorrect
2 Halted 0 ms 0 KB -