제출 #1169646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169646		huutuan	Toxic Gene (NOI23_toxic)	C++20	67.60 / 100	8 ms	496 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;
   int tid=0;
   vector<int> v;
   auto query8=[&](int sz){
      vector<int> vv;
      for (int i=0; i<sz; ++i){
         int j=1<<i;
         while (j--) vv.push_back(v[i]);
      }
      int x=fake_query_sample(vv);
      if (x==(int)vv.size()){
         for (int i=0; i<sz; ++i) vsr.push_back(v[i]);
      }else{
         vector<int> vrt;
         for (int i=0; i<sz; ++i){
            if (x>>i&1){
               answer[v[i]]='S';
            }else{
               vrt.push_back(v[i]);
            }
         }
         int l=1, r=(int)vrt.size()-1;
         while (l<=r){
            int mid=(l+r)>>1;
            if (fake_query_sample(vector<int>(vrt.begin(), vrt.begin()+mid))) l=mid+1;
            else r=mid-1;
         }
         answer[vrt[r]]='T';
         tid=vrt[r];
         vrt.erase(vrt.begin(), vrt.begin()+l);
         v.insert(v.end(), vrt.begin(), vrt.end());
      }
      v.erase(v.begin(), v.begin()+sz);
   };
   auto query8_2=[&](int sz){
      vector<int> vv={tid};
      for (int i=0; i<sz; ++i){
         int j=1<<i;
         while (j--) vv.push_back(vsr[i]);
      }
      int x=fake_query_sample(vv);
      for (int i=0; i<sz; ++i){
         if (x>>i&1){
            answer[vsr[i]]='S';
         }
      }
      vsr.erase(vsr.begin(), vsr.begin()+sz);
   };
   v.resize(n);
   iota(v.begin(), v.end(), 1);
   while (v.size()) query8(min(8, (int)v.size()));
   while (vsr.size()) query8_2(min(8, (int)vsr.size()));
   for (int i=1; i<=n; ++i) fake_answer_type(i, answer[i]);
}

• Subtask 1: 67.6 / 100