Submission #1182760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182760		asli_bg	Toxic Gene (NOI23_toxic)	C++20	0 / 100	3 ms	324 KiB

toxic

#include<bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

//#define int long long

#include "toxic.h"

typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<bool> vb;

#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pb push_back
#define sp <<" "<<

#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;

#define DEBUG(x) cout<<#x sp x<<endl;
#define carp(x,y) ((x%MOD)*(y%MOD))%MOD
#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
#define mid (l+r)/2

void determine_type(int n){

    vector<char> ans(n+1);

    vi vec;
    vi bir,iki;

    for(int i=1;i<=n;i+=8){
        FORE(j,i,min(n+1,i+8)) vec.pb(j);
        int deg=query_sample(vec);
        if(deg==8){
            //no toxic
            bir.pb(i);
        }
        else{
            //toxic
            iki.pb(i);
        }
        vec.clear();
    }
    
    vi vv;
    set<int> s;
    int tt;

    //toxic
    for(auto el:iki){
        vv.clear();s.clear();vec.clear();
        FORE(i,el,min(n+1,el+8)) {s.insert(i); vv.pb(i);}

        bool f=true;
        while(f){
            f=false;

            int l=-1;
            int r=s.size();
            while(l+1<r){
                FORE(i,l,mid+1) if(i>=0) vec.pb(vv[i]);
                int deg=query_sample(vec);
                if(deg==vec.size()){
                    //no toxic at the first half
                    l=mid;
                }
                else{
                    //toxic in first half
                    r=mid;
                }
                vec.clear();
            }

            if(r<s.size()){
                tt=vv[r];
                ans[vv[r]]='T';
                s.erase(vv[r]);
                vv.clear();
                for(auto el:s) vv.pb(el);
            }

            int deg=query_sample(vv);
            if(deg<vv.size()) f=true; //hala toxic var
        }

        int sz=vv.size();

        vec.pb(tt);

        FOR(i,sz){
            FOR(j,(1<<i)){
                vec.pb(vv[i]);
            }
        }

        int deg=query_sample(vec);

        for(int bt=0;bt<sz;bt++){
            if(deg&(1<<bt)){
                //(bt+el). strongmuş
                ans[vv[bt]]='S';
            }
            else ans[vv[bt]]='R';
        }
    }

    //no toxic
    for(auto el:bir){
        vec.pb(tt);
        FORE(i,el,min(n+1,el+8)){
            FOR(j,(1<<(i-el))){
                vec.pb(i);
            }
        }
        int deg=query_sample(vec);

        for(int bt=0;bt<8;bt++){
            if(deg&(1<<bt)){
                //(bt+el). strongmuş
                ans[bt+el]='S';
            }
            else ans[bt+el]='R';
        }
        vec.clear();
    }

    FORE(i,1,n+1){
        answer_type(i,ans[i]);
    }
}

• Subtask 1: 0 / 100