제출 #1169656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169656		huutuan	Toxic Gene (NOI23_toxic)	C++20	100 / 100	13 ms	504 KiB

toxic

#include "toxic.h"

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(1);

void determine_type(int n){
   vector<int> toxic;
   vector<int> strong, regular;
   vector<int> v(n); iota(v.begin(), v.end(), 1);
   vector<int> v2;
   int cnt=0;
   while (v.size()){
      shuffle(v.begin(), v.end(), rng);
      vector<int> dead, vv;
      while (vv.size()<8 && v.size()){
         vv.push_back(v.back());
         v.pop_back();
      }
      vector<int> query;
      for (int j=0; j<(int)vv.size(); ++j){
         for (int k=0; k<(1<<j); ++k) query.push_back(vv[j]);
      }
      int t=query.size();
      if (cnt!=30){
         t=query_sample(query);
      }
      if (t==((1<<(int)vv.size())-1)){
         v2.insert(v2.end(), vv.begin(), vv.end());
      }else{
         for (int j=0; j<(int)vv.size(); ++j) if (t>>j&1) strong.push_back(vv[j]); else dead.push_back(vv[j]);
         vv.clear();
         int l=0, r=dead.size()-2;
         while (l<=r){
            int mid=(l+r)>>1;
            query=vector<int>(dead.begin(), dead.begin()+mid+1);
            while ((int)vv.size()<8 && v2.size()) vv.push_back(v2.back()), v2.pop_back();
            for (int k=0; k<(int)vv.size(); ++k){
               for (int _=0; _<(1<<k); ++_) query.push_back(vv[k]);
            }
            int tmp=query.size();
            if (cnt!=30){
               tmp=query_sample(query);
            }
            if (tmp!=(int)query.size()){
               for (int k=0; k<(int)vv.size(); ++k) if (tmp>>k&1) strong.push_back(vv[k]); else regular.push_back(vv[k]);
               vv.clear();
               r=mid-1;
            }else l=mid+1;
         }
         for (int j=0; j<l; ++j) regular.push_back(dead[j]);
         toxic.push_back(dead[l]);
         dead.erase(dead.begin(), dead.begin()+l+1);
         ++cnt;
         if (vv.size()) v2.insert(v2.end(), vv.begin(), vv.end());
         v.insert(v.end(), dead.begin(), dead.end());
      }
   }
   v=v2;
   while (v.size()){
      shuffle(v.begin(), v.end(), rng);
      vector<int> vv;
      while (vv.size()<8 && v.size()){
         vv.push_back(v.back());
         v.pop_back();
      }
      vector<int> query{toxic[0]};
      for (int k=0; k<(int)vv.size(); ++k){
         for (int l=0; l<(1<<k); ++l) query.push_back(vv[k]);
      }
      int t=query_sample(query);
      for (int k=0; k<(int)vv.size(); ++k) if (t>>k&1) strong.push_back(vv[k]); else regular.push_back(vv[k]);
   }
   for (int i:regular) answer_type(i, 'R');
   for (int i:strong) answer_type(i, 'S');
   for (int i:toxic) answer_type(i, 'T');
}

• Subtask 1: 100 / 100