oj.uz

Submission #1025422

# Submission time Handle Problem Language Result Execution time Memory
1025422 2024-07-17T03:04:05 Z huutuan The Big Prize (IOI17_prize) C++14
0 / 100
 1000 ms 14508 KB 
#include "prize.h"

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

vector<int> mem[200000];

vector<int> Ask(int i){
   if (mem[i].size()) return mem[i];
   return mem[i]=ask(i);
}

int find_best(int n) {
   for (int i=0; i<n; ++i) mem[i].clear();
   if (n<=5000){
      for (int i=0; i<n; ++i){
         auto tmp=ask(i);
         if (tmp[0]+tmp[1]==0) return i;
      }
      return -1;
   }
   int m=n;
   int mx=0;
   while (m>1){
      m=(int)sqrt(m);
      mx+=m;
   }
   vector<pair<int, int>> v(mx);
   for (int i=0; i<mx; ++i){
      auto tmp=Ask(i);
      v[i]={tmp[0], tmp[1]};
      if (tmp[0]+tmp[1]==0) return i;
   }
   int cnt=0;
   for (auto &i:v) cnt=max(cnt, i.first+i.second);
   ordered_set<int> st, id;
   for (int i=0; i<mx; ++i) if (v[i].first+v[i].second!=cnt) id.insert(i);
   for (int i=mx; i<n; ++i) st.insert(i);
   int rem=cnt-(int)id.size();
   while (rem){
      int l=0, r=(int)st.size()-1;
      while (l<=r){
         int mid=(l+r)>>1;
         auto tmp=Ask(mid);
         if (tmp[0]+tmp[1]!=cnt){
            id.insert(mid);
            st.erase(mid);
            --rem;
            break;
         }
         int cntl=tmp[0];
         cntl-=id.order_of_key(mid);
         if (cntl) r=mid;
         else l=mid+1;
      }
   }
   for (int i:id){
      auto tmp=Ask(i);
      if (tmp[0]+tmp[1]==0) return i;
   }
   return -1;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 14288 KB Output is correct
2 Correct 95 ms 14324 KB Output is correct
3 Correct 86 ms 14420 KB Output is correct
4 Execution timed out 3036 ms 14416 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 14488 KB Output is correct
2 Correct 83 ms 14416 KB Output is correct
3 Correct 78 ms 14508 KB Output is correct
4 Execution timed out 3068 ms 14416 KB Time limit exceeded
5 Halted 0 ms 0 KB -