| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 977755 | CSQ31 | Toxic Gene (NOI23_toxic) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "toxic.h"
#include <string>
#include <cassert>
#include <vector>
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
namespace {
static void wrong_answer(){
printf("%d\n",-1);
exit(0);
}
static int tc, current_tc, N, batchsize = 300, qlimit = 600;
static int q[105];
static char answer[105][305];
static char participant_type[105][305];
}
int query_sample(vector<int> species){
if (species.size() > batchsize){
wrong_answer();
}
q[current_tc]++;
if (q[current_tc] > qlimit){
wrong_answer();
}
bool has_toxic = false;
int reg = 0, strong = 0;
for (int i = 0; i < (int) species.size(); ++i){
if (species[i] < 1 || species[i] > N){
wrong_answer();
}
char tp = answer[current_tc][species[i]];
if (tp == 'T'){
has_toxic = true;
}
if (tp == 'R'){
reg++;
}
if (tp == 'S'){
strong++;
}
}
if (has_toxic) return strong;
else return reg + strong;
}
void answer_type(int x, char c){
//cout<<x<<" "<<c<<'\n';
if (x < 1 || x > N) wrong_answer();
if (c != 'T' && c != 'R' && c != 'S') wrong_answer();
participant_type[current_tc][x] = c;
if (participant_type[current_tc][x] != answer[current_tc][x]) wrong_answer();
}
#define sz(a) (int)(a.size())
mt19937 seed(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand2(int l,int r){return uniform_int_distribution<int>(l,r)(seed);}
vector<int>tox;
vector<int>leftover;
vector<int>notox;
int bquery(vector<int>v){
int ori = sz(v);
int c = min(8,sz(notox));
vector<int>add;
for(int i=0;i<c;i++){
int x = notox.back();
add.push_back(x);
notox.pop_back();
for(int j=0;j<(1<<i);j++)v.push_back(x);
}
int res = query_sample(v);
if(res == sz(v)){
for(int x:add)notox.push_back(x);
return ori;
}else{
for(int i=0;i<c;i++){
if(res & (1<<i))answer_type(add[i],'S');
else answer_type(add[i],'R');
}
return 0;
}
}
void find_toxic(vector<int>v){
// for(int x:v)cout<<x<<" ";
// cout<<'\n';
if(sz(v) == 1){
//cout<<v[0]<<'\n';
answer_type(v[0],'T');
tox.push_back(v[0]);
return;
}
int m = sz(v)/2;
vector<int>a,b;
for(int i=0;i<m;i++)a.push_back(v[i]);
for(int i=m;i<sz(v);i++)b.push_back(v[i]);
if(rand2(0,1))swap(a,b);
int res = bquery(a);
if(res == sz(a)){
for(int x:a)answer_type(x,'R');
find_toxic(b);
}
else {
for(int x:b)leftover.push_back(x);
find_toxic(a);
}
}
void determine_type(int n){
vector<int>p;
for(int i=1;i<=n;i++)p.push_back(i);
shuffle(p.begin(),p.end(),seed);
notox.clear();
tox.clear();
vector<vector<int>>maybe;
for(int i=1;i<=n;i+=8){
vector<int>v;
for(int j=0;j<8;j++){
if(i+j > n)break;
for(int k=0;k<(1<<j);k++)v.push_back(p[i+j-1]);
}
int res = query_sample(v);
if(res == sz(v)){
for(int j=0;j<8;j++){
if(i+j > n)break;
notox.push_back(p[i+j-1]);
}
}else{
vector<int>u;
for(int j=0;j<8;j++){
if(i+j > n)break;
if(res & (1<<j))answer_type(p[i+j-1],'S');
else u.push_back(p[i+j-1]);
}
maybe.push_back(u);
}
}
while(!maybe.empty()){
vector<int>v = maybe.back();
maybe.pop_back();
int lim = 8;
if(sz(tox) >= 15)lim = 16;
//if(sz(tox) >= 20)lim = 32;
while(!maybe.empty() && sz(v) + sz(maybe.back()) <= lim){
vector<int>u = maybe.back();
for(int x:u)v.push_back(x);
maybe.pop_back();
}
while(true){
leftover.clear();
find_toxic(v);
v = leftover;
if(v.empty())break;
if(bquery(v)){
for(int x:v)answer_type(x,'R');
break;
}
}
}
// cout<<"TES"<<'\n';
//query left out regular/strong
while(!notox.empty()){
vector<int>v;
int c = min(8,sz(notox));
vector<int>add;
for(int i=0;i<c;i++){
int x = notox.back();
add.push_back(x);
notox.pop_back();
for(int j=0;j<(1<<i);j++)v.push_back(x);
}
v.push_back(tox[0]);
int res = query_sample(v);
for(int i=0;i<c;i++){
if(res & (1<<i))answer_type(add[i],'S');
else answer_type(add[i],'R');
}
}
}
int main(){
assert(2 == scanf("%d %d\n",&tc,&N));
for (int t = 1; t <= tc; ++t){
assert(1 == scanf("%s",answer[t]));
for (int i = N; i >= 1; --i){
answer[t][i] = answer[t][i-1];
// if(answer[t][i] == 'T')cout<<i<<'\n';
}
answer[t][0] = 'X';
for (int i = 1; i <= N; ++i){
participant_type[t][i] = 'X';
}
}
for (int t = 1; t <= tc; ++t){
current_tc = t;
q[current_tc] = 0;
determine_type(N);
for (int i = 1; i <= N; ++i){
if (participant_type[current_tc][i] != answer[current_tc][i]) wrong_answer();
}
}
for (int t = 1; t <= tc; ++t){
printf("%d\n",q[t]);
}
return 0;
}
//43 120 139 166 169 223 240 250 265 266 274 280 69 80 102 139 245 268 269 282 298 299