oj.uz

Submission #1025441

# Submission time Handle Problem Language Result Execution time Memory
1025441 2024-07-17T03:35:10 Z huutuan The Big Prize (IOI17_prize) C++14
20 / 100
 73 ms 9368 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> id;
   vector<int> st;
   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.push_back(i);
   auto solve=[&](auto &&self, vector<int> pos, int cc){
      if (!cc || pos.empty()) return;
      int mid=((int)pos.size()-1)/2;
      vector<int> posl, posr;
      for (int j:pos){
         if (j<pos[mid]) posl.push_back(j);
         if (j>pos[mid]) posr.push_back(j);
      }
      auto tmp=ask(pos[mid]);
      if (tmp[0]+tmp[1]!=cnt){
         id.insert(pos[mid]);
         int l=mid, r=mid;
         while (l){
            --l;
            auto tmp2=ask(pos[l]);
            if (tmp2[0]+tmp2[1]!=cnt) id.insert(pos[l]), posl.pop_back();
            else{
               int cl=tmp2[0]-id.order_of_key(pos[l]);
               int cr=tmp2[1]-((int)id.size()-id.order_of_key(pos[l]));
               self(self, posl, cl);
               self(self, posr, cr);
               return;
            }
         }
         while (r+1<(int)pos.size()){
            ++r;
            reverse(posr.begin(), posr.end());
            auto tmp2=ask(pos[r]);
            if (tmp2[0]+tmp2[1]!=cnt) id.insert(pos[r]), posr.pop_back();
            else{
               reverse(posr.begin(), posr.end());
               int cl=tmp2[0]-id.order_of_key(pos[r]);
               int cr=tmp2[1]-((int)id.size()-id.order_of_key(pos[r]));
               self(self, posl, cl);
               self(self, posr, cr);
               return;
            }
         }
      }else{
         int cl=tmp[0]-id.order_of_key(pos[mid]);
         int cr=tmp[1]-((int)id.size()-id.order_of_key(pos[mid]));
         self(self, posl, cl);
         self(self, posr, cr);
      }
   };
   solve(solve, st, cnt-(int)id.size());
   for (int i:id){
      auto tmp=Ask(i);
      if (tmp[0]+tmp[1]==0) return i;
   }
   return -1;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9164 KB Output is correct
2 Correct 7 ms 9160 KB Output is correct
3 Correct 12 ms 8908 KB Output is correct
4 Correct 8 ms 9164 KB Output is correct
5 Correct 6 ms 9160 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 7 ms 9164 KB Output is correct
8 Correct 9 ms 9068 KB Output is correct
9 Correct 9 ms 9164 KB Output is correct
10 Correct 9 ms 8908 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9084 KB Output is correct
2 Correct 8 ms 9096 KB Output is correct
3 Correct 8 ms 8908 KB Output is correct
4 Correct 8 ms 8908 KB Output is correct
5 Correct 9 ms 9096 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 11 ms 8888 KB Output is correct
8 Correct 9 ms 9080 KB Output is correct
9 Correct 9 ms 9108 KB Output is correct
10 Correct 8 ms 9164 KB Output is correct
11 Correct 24 ms 9164 KB Output is correct
12 Correct 27 ms 9048 KB Output is correct
13 Correct 26 ms 9164 KB Output is correct
14 Correct 14 ms 5464 KB Output is correct
15 Incorrect 73 ms 9368 KB Incorrect
16 Halted 0 ms 0 KB -