oj.uz

답안 #1025444

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1025444 2024-07-17T03:36:04 Z huutuan 커다란 상품 (IOI17_prize) C++14
20 / 100
 63 ms 9168 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;
            }
         }
         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]));
         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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 9164 KB Output is correct
2 Correct 7 ms 9164 KB Output is correct
3 Correct 8 ms 9092 KB Output is correct
4 Correct 8 ms 8908 KB Output is correct
5 Correct 7 ms 9164 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 6 ms 9164 KB Output is correct
8 Correct 6 ms 9164 KB Output is correct
9 Correct 8 ms 8932 KB Output is correct
10 Correct 6 ms 9164 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9164 KB Output is correct
2 Correct 6 ms 9164 KB Output is correct
3 Correct 6 ms 8908 KB Output is correct
4 Correct 6 ms 9164 KB Output is correct
5 Correct 6 ms 9096 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 8 ms 9164 KB Output is correct
8 Correct 7 ms 9164 KB Output is correct
9 Correct 5 ms 8908 KB Output is correct
10 Correct 6 ms 9164 KB Output is correct
11 Correct 18 ms 9164 KB Output is correct
12 Correct 18 ms 9164 KB Output is correct
13 Correct 16 ms 9164 KB Output is correct
14 Correct 13 ms 5464 KB Output is correct
15 Incorrect 63 ms 9168 KB Incorrect
16 Halted 0 ms 0 KB -