Submission #941248

#	Time	Username	Problem	Language	Result	Execution time	Memory
941248		abcvuitunggio	Toxic Gene (NOI23_toxic)	C++17	45.48 / 100	5 ms	508 KiB

toxic

#ifndef NAM
#include "toxic.h"
#endif // NAM
#include <bits/stdc++.h>
using namespace std;
#ifdef NAM
string s;
int cnt_q,ch[301];
int query_sample(vector <int> species){
    cnt_q++;
    if (species.size()>300){
        cout << "Error: Species size too large";
        exit(0);
    }
    bool has_toxic=0;
    int cnt=0;
    for (int i:species)
        if (s[i-1]=='T')
            has_toxic=1;
    for (int i:species)
        cnt+=(s[i-1]=='S'||(s[i-1]=='R'&&!has_toxic));
    return cnt;
}
void answer_type(int x, char c){
    if (ch[x]){
        cout << "Answer position " << x << "twice";
        exit(0);
    }
    ch[x]=1;
    if (s[x-1]!=c){
        cout << "Wrong answer on character " << x;
        exit(0);
    }
}
#endif // NAM
vector <int> toxic,non_toxic;
int T[301];
int ask(int l, int r){
    vector <int> v;
    for (int i=l;i<=r;i++)
        v.push_back(i);
    return query_sample(v);
}
void solve(int l, int r){
    if (ask(l,r)==r-l+1)
        return;
    if (l>r)
        return;
    int lo=l,hi=r-1,kq=r;
    while (lo<=hi){
        int mid=(lo+hi)>>1;
        if (ask(l,mid)<mid-l+1){
            kq=mid;
            hi=mid-1;
        }
        else
            lo=mid+1;
    }
    toxic.push_back(kq);
    T[kq]=1;
    solve(kq+1,r);
}
void determine_type(int n){
    memset(T,0,sizeof(T));
    toxic.clear();
    non_toxic.clear();
    int sz=8;
    for (int i=1;i<=n;i+=sz)
        solve(i,min(i+sz-1,n));
    for (int i:toxic)
        answer_type(i,'T');
    for (int i=1;i<=n;i++)
        if (!T[i])
            non_toxic.push_back(i);
    for (int j=0;j<non_toxic.size();j+=8){
        vector <int> ve;
        for (int i=0;i<8&&i+j<non_toxic.size();i++)
            for (int k=0;k<(1<<i);k++)
                ve.push_back(non_toxic[i+j]);
        ve.push_back(toxic[0]);
        int x=query_sample(ve);
        for (int i=0;i<8&&i+j<non_toxic.size();i++)
            answer_type(non_toxic[i+j],((x>>i)&1?'S':'R'));
    }
}
#ifdef NAM
int main(){
    mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
    //cin >> s;
    int tc=100,mx=0;
    while (tc--){
        s="";
        cnt_q=0;
        memset(ch,0,sizeof(ch));
        vector <int> tmp;
        for (int i=0;i<300;i++){
            s+=(rd()&1?'R':'S');
            tmp.push_back(i);
        }
        for (int i=0;i<30;i++)
            s[rd()%s.size()]='T';
        determine_type(s.size());
        for (int i=1;i<=s.size();i++)
            if (!ch[i]){
                cerr << "Didn't answer position " << i;
                exit(0);
            }
        mx=max(mx,cnt_q);
    }
    cout << "You used " << mx << " queries";
}
#endif // NAM

Compilation message (stderr)

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int j=0;j<non_toxic.size();j+=8){
      |                  ~^~~~~~~~~~~~~~~~~
toxic.cpp:77:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int i=0;i<8&&i+j<non_toxic.size();i++)
      |                           ~~~^~~~~~~~~~~~~~~~~
toxic.cpp:82:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for (int i=0;i<8&&i+j<non_toxic.size();i++)
      |                           ~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 45.48235294 / 100