제출 #1185159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185159		epicci23	Toxic Gene (NOI23_toxic)	C++20	38.75 / 100	6 ms	500 KiB

toxic

#include "bits/stdc++.h"
#include "toxic.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int ask(vector<int> v){
  return query_sample(v);
}

void determine_type(int n){
	vector<int> Toxic;
	
    vector<int> Mapping;
    for(int i=1;i<=n;i++) Mapping.push_back(i);
    shuffle(all(Mapping), rng);

	for(int i = 1; i <= n; i+=3){
      vector<int> xd;
      for(int j = i; j <= min(n, i + 2); j++) xd.push_back(Mapping[j - 1]);
      int hm = ask(xd);
      if(hm < sz(xd)){

        bool ok = 0;

        for(int u = 0; u < sz(xd); u++){

         if(ok == 0 && u == sz(xd) - 1){
           Toxic.push_back(xd[u]);
           break;
         }

         if(ask({xd[u]}) == 0){
           ok = 1;
           Toxic.push_back(xd[u]);
         }

        }
      }
	}
    
    vector<int> mark(n+5,0);
    for(int u : Toxic) mark[u] = 1;

    vector<int> Calc;
    for(int i=1;i<=n;i++) if(!mark[i]) Calc.push_back(i);

    while(!Calc.empty()){
      vector<int> Tek,Ogren;
      Tek.push_back(Toxic[0]);

      while(sz(Ogren) < 8 && !Calc.empty()){
      	int cur = Calc.back();
      	Calc.pop_back();
      	for(int j = 0; j < (1<<(sz(Ogren))); j++) Tek.push_back(cur);
        Ogren.push_back(cur);
      }

      int mask = ask(Tek);
      for(int i = 0; i < sz(Ogren); i++) if(mask >> i & 1) mark[Ogren[i]] = 2;
    }

    for(int i=1;i<=n;i++){
      if(mark[i] == 0) answer_type(i, 'R');
      else if(mark[i] == 1) answer_type(i, 'T');
      else answer_type(i, 'S');
    }
}

• Subtask 1: 38.7529 / 100