Submission #1169636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169636		huutuan	Toxic Gene (NOI23_toxic)	C++20	44.45 / 100	7 ms	328 KiB

toxic

#include "toxic.h"

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(69420);

void determine_type(int n){
   vector<int> mp(n+1);
   iota(mp.begin(), mp.end(), 0);
   // shuffle(mp.begin()+1, mp.end(), rng);
   vector<int> answer(n+1, 'R');
   auto fake_query_sample=[&](vector<int> v) -> int {
      for (int &i:v) i=mp[i];
      return query_sample(v);
   };
   auto fake_answer_type=[&](int x, char c) -> void {
      return answer_type(mp[x], c);
   };
   auto query=[&](int l, int r) -> int {
      vector<int> v(r-l+1);
      iota(v.begin(), v.end(), l);
      return fake_query_sample(v);
   };
   vector<int> vsr;
   vector<vector<int>> vrt;
   auto query8=[&](int l, int r){
      vector<int> v;
      for (int i=l; i<=r; ++i){
         int j=1<<(i-l);
         while (j--) v.push_back(i);
      }
      int x=fake_query_sample(v);
      if (x==(int)v.size()){
         for (int i=l; i<=r; ++i) vsr.push_back(i);
      }else{
         vrt.emplace_back();
         for (int i=l; i<=r; ++i){
            if (x>>(i-l)&1){
               answer[i]='S';
            }else{
               vrt.back().push_back(i);
            }
         }
      }
   };
   auto query8_2=[&](int l, int r){
      vector<int> v=vrt[0];
      for (int i=l; i<=r; ++i){
         int j=1<<(i-l);
         while (j--) v.push_back(vsr[i]);
      }
      int x=fake_query_sample(v);
      for (int i=l; i<=r; ++i){
         if (x>>(i-l)&1){
            answer[vsr[i]]='S';
         }
      }
   };
   for (int i=1; i<=n; i+=8) query8(i, min(n, i+7));
   for (int i=0; i<(int)vsr.size(); i+=8) query8_2(i, min((int)vsr.size()-1, i+7));
   for (auto &i:vrt){
      while (i.size() && !fake_query_sample(vector<int>(i.begin(), i.end()))){
         int l=1, r=(int)i.size()-1;
         while (l<=r){
            int mid=(l+r)>>1;
            if (fake_query_sample(vector<int>(i.begin(), i.begin()+mid))) l=mid+1;
            else r=mid-1;
         }
         answer[i[r]]='T';
         i.erase(i.begin(), i.begin()+l);
      }
   }
   for (int i=1; i<=n; ++i) fake_answer_type(i, answer[i]);
}

• Subtask 1: 44.4471 / 100