Submission #1185140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185140		epicci23	Toxic Gene (NOI23_toxic)	C++20	28.14 / 100	7 ms	328 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;

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

vector<int> Toxic;

int dfs(int l,int r,int fl){
  if(sz(Toxic) == 30 || l > r) return 0;
  // fl -> burada kesin bir tane toxic var mi
  if(!fl){
   vector<int> hm;
   for(int i=l;i<=r;i++) hm.push_back(i);
   int lol = ask(hm);
   if(lol == r - l + 1) return 0;
  }

  if(l == r){
  	Toxic.push_back(l);
  	return 1;
  }
  
  int mid = (l + r) / 2;
  int xd = dfs(l, mid, 0);
  int xd2 = dfs(mid + 1, r, !xd);

  return 1;
}


void determine_type(int n){
	Toxic.clear();
	dfs(1, n, 1);
    
    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: 28.1412 / 100