oj.uz

답안 #1025445

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1025445 2024-07-17T03:38:01 Z huutuan 커다란 상품 (IOI17_prize) C++14
20 / 100
 70 ms 9176 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]));
         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 9108 KB Output is correct
2 Correct 7 ms 9036 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 9164 KB Output is correct
6 Correct 1 ms 4948 KB Output is correct
7 Correct 9 ms 9164 KB Output is correct
8 Correct 7 ms 9164 KB Output is correct
9 Correct 8 ms 9164 KB Output is correct
10 Correct 8 ms 8908 KB Output is correct

Subtask #2
0 / 80.0

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