제출 #1182862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182862		asli_bg	Toxic Gene (NOI23_toxic)	C++20	44.45 / 100	3 ms	328 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){
    vi a;
    FORE(i,1,n+1) a.pb(i);

    vector<char> ans(n+1);
    random_shuffle(all(a));

    vi vec;
    vi bir,iki;

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

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

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

            int l=0;
            int r=s.size()-1;
            while(l<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+1;
                }
                else{
                    //toxic in first half
                    r=mid;
                }
                vec.clear();
            }

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

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

        int sz=vv.size();

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

            vec.pb(tt);

            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.clear();
        vec.pb(tt);
        FORE(i,el,min(n,el+8)){
            FOR(j,(1<<(i-el))){
                vec.pb(a[i]);
            }
        }

        int deg=query_sample(vec);

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

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

• Subtask 1: 44.4471 / 100