제출 #1169597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169597		huutuan	Toxic Gene (NOI23_toxic)	C++20	44.96 / 100	8 ms	500 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);
   };
   int id_t=0;
   {
      int l=1, r=n-1;
      while (l<=r){
         int mid=(l+r)>>1;
         if (query(1, mid)!=mid) r=mid-1;
         else l=mid+1;
      }
      id_t=l;
   }
   auto query8=[&](int l, int r){
      vector<int> v{id_t};
      for (int i=l; i<=r; ++i){
         int j=1<<(i-l);
         while (j--) v.push_back(i);
      }
      int x=fake_query_sample(v);
      for (int i=l; i<=r; ++i){
         if (x>>(i-l)&1){
            answer[i]='S';
         }
      }
   };
   for (int i=1; i<=n; i+=8) query8(i, min(n, i+7));
   vector<int> idx;
   for (int i=1; i<=n; ++i) if (answer[i]=='R') idx.push_back(i);
   while (idx.size()){
      int sz=min(8, (int)idx.size());
      vector<int> v(idx.begin(), idx.begin()+sz);
      if (fake_query_sample(v)==v.size()){
         idx.erase(idx.begin(), idx.begin()+sz);
         continue;
      }
      int l=1, r=sz-1;
      while (l<=r){
         int mid=(l+r)>>1;
         if (fake_query_sample(vector<int>(idx.begin(), idx.begin()+mid))==mid) l=mid+1;
         else r=mid-1;
      }
      answer[idx[r]]='T';
      idx.erase(idx.begin(), idx.begin()+l);
   }
   for (int i=1; i<=n; ++i) fake_answer_type(i, answer[i]);
}

• Subtask 1: 44.9647 / 100