Submission #1030914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030914		huutuan	The Big Prize (IOI17_prize)	C++14	100 / 100	178 ms	187588 KiB

prize

#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 cnt=0;
   {
      auto tmp=Ask(0);
      cnt=tmp[0]+tmp[1];
   }
   if (!cnt) return 0;
   ordered_set<int> id;
   vector<int> st;
   for (int i=1; 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){
         cnt=tmp[0]+tmp[1];
         st.clear();
         for (int i=0; i<n; ++i) if (mem[i].size()){
            if (mem[i][0]+mem[i][1]<cnt) id.insert(i);
         }else st.push_back(i);
         self(self, st, cnt-(int)id.size());
      }if (tmp[0]+tmp[1]!=cnt){
         id.insert(pos[mid]);
         pos.erase(pos.begin()+mid);
         self(self, pos, cc-1);
      }else{
         int cl=tmp[0]-id.order_of_key(pos[mid]);
         int cr=cc-cl;
         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 / 20
• Subtask 2: 80 / 80