oj.uz

Submission #1025447

# Submission time Handle Problem Language Result Execution time Memory
1025447 2024-07-17T03:39:08 Z huutuan The Big Prize (IOI17_prize) C++14
20 / 100
 11 ms 17100 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]);
         pos.erase(pos.begin()+mid);
         self(self, pos, cc-1);
         // 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;
         //    }
         // }
         // reverse(posr.begin(), posr.end());
         // while (r+1<(int)pos.size()){
         //    ++r;
         //    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]));
         assert(cl+cr==cc);
         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 6 ms 8908 KB Output is correct
2 Correct 8 ms 9096 KB Output is correct
3 Correct 7 ms 9164 KB Output is correct
4 Correct 7 ms 8908 KB Output is correct
5 Correct 9 ms 9104 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 7 ms 8908 KB Output is correct
8 Correct 6 ms 9164 KB Output is correct
9 Correct 6 ms 9164 KB Output is correct
10 Correct 7 ms 8908 KB Output is correct

Subtask #2
0 / 80.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 8 ms 9164 KB Output is correct
4 Correct 7 ms 9164 KB Output is correct
5 Correct 7 ms 9104 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 7 ms 9164 KB Output is correct
8 Correct 7 ms 9164 KB Output is correct
9 Correct 7 ms 9164 KB Output is correct
10 Correct 6 ms 9164 KB Output is correct
11 Runtime error 11 ms 17100 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -