Submission #1169564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169564		huutuan	Toxic Gene (NOI23_toxic)	C++20	7.06 / 100	4 ms	328 KiB

toxic

#include "toxic.h"

#include <bits/stdc++.h>

using namespace std;

void determine_type(int n){
   vector<int> ct(n*4, -1), cr(n*4, -1), ctr(n*4, -1), cs(n*4, -1);
   auto query=[&](int l, int r) -> int {
      vector<int> v(r-l+1);
      iota(v.begin(), v.end(), l);
      return 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 query_t=[&](int l, int r) -> int {
      vector<int> v(r-l+1);
      iota(v.begin(), v.end(), l);
      if (id_t<l || r<id_t){
         v.push_back(id_t);
      }
      return query_sample(v);
   };
   auto dnc_t=[&](auto &&self, int k, int l, int r) -> void {
      int c=query(l, r);
      if (c){
         for (int i=l; i<=r; ++i) answer_type(i, 'R');
         return;
      }
      if (l==r){
         answer_type(l, 'T');
         return;
      }
      int mid=(l+r)>>1;
      self(self, k<<1, l, mid);
      self(self, k<<1|1, mid+1, r);
   };
   auto dnc=[&](auto &&self, int k, int l, int r) -> void {
      if (cs[k]==-1) cs[k]=query_t(l, r);
      if (cs[k]==r-l+1){
         for (int i=l; i<=r; ++i) answer_type(i, 'S');
         return;
      }
      if (cs[k]==0) return dnc_t(dnc_t, k, l, r);
      assert(l!=r);
      int mid=(l+r)>>1;
      self(self, k<<1, l, mid);
      cs[k<<1|1]=cs[k]-cs[k<<1];
      self(self, k<<1|1, mid+1, r);
   };
   dnc(dnc, 1, 1, n);
}

• Subtask 1: 7.0615 / 100