제출 #1155485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155485		modwwe	Toxic Gene (NOI23_toxic)	C++20	93.25 / 100	9 ms	328 KiB

toxic

//#include "gap.h"
//#include "mushrooms.h"
//#include "prize.h"
#include "toxic.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(324857235);
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf = 1e16;
const ll mod2 = 1e9+7;
const ll base=67;
int  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7;
int kk;
int t;
int el = 19;/*
main()
{
    if(fopen(task2".inp","r"))
    {
        fin(task2);
        fou(task2);
    }
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    /// cin>>s1;
//int t;cin>>t; while(t--)
    phongbeo();
    checktime
}*/
vector<int> per,v[40],huhu[40],haha[40];
int c[301];
int color[301];
/*int query_sample(vector<int> v)
{
    dem4++;
    bool de=0;
    dem=0;
    for(auto x:v)
    {
        if(color[x]==1)dem++;
        if(color[x]==2)de=1;
    }
    if(de) return dem;
    return v.size();
}*/
void fc(vector<int> a,int x)
{
    for(int i=0; i<8; i++)
        if(mask(i)-1<a.size())
        {
            if(bit(x,i))c[a[mask(i)-1]]=1;
            else c[a[mask(i)-1]]=0;
        }
}
void fhaha(vector<int> a,int x)
{
    vector<int> ask;
    for(int i=0; i<a.size(); i++)
        ask.pb(a[i]);
    ask.pb(x);
    s2=query_sample(ask);
    fc(a,s2);
}
void xix(vector<int> a)
{
    l=0;
    r=a.size()-2;
    while(l<=r)
    {
        int mid=l+r>>1;
        vector<int> ask;
        for(int i=0; i<=mid; i++)
            ask.pb(a[i]);
        if(dem6>=0)
        {
            for(auto x:haha[dem6])
                ask.pb(x);
        }
        int s=query_sample(ask);
        if(s==ask.size())l=mid+1;
        else
        {
            if(dem6>=0)
            {
                fc(haha[dem6],s);
                dem6--;
            }
            r=mid-1;
        }
    }
    for(int i=0; i<l; i++)c[a[i]]=0;
    c[a[l]]=2;
    vector<int> ask,nxt;
    for(int i=l+1; i<a.size(); i++)
        nxt.pb(a[i]),ask.pb(a[i]);
    if(nxt.size()==0) return;
    if(dem6>=0)
    {
        for(auto x:haha[dem6])
            ask.pb(x);
    }
    int s=query_sample(ask);
    if(s!=ask.size())
    {
        if(dem6>=0)fc(haha[dem6],s),dem6--;
        xix(nxt);
    }
}
void work(vector<int> a)
{
    vector<int> ask;
    for(int i=0; i<a.size(); i++)
        for(int j=1; j<=mask(i); j++)
            ask.pb(a[i]);
    s2=query_sample(ask);
    if(s2==ask.size())
    {
        for(auto x:ask)
            haha[dem6].pb(x);
        dem6++;
        return;
    }
    for(int i=0; i<a.size(); i++)
        if(!bit(s2,i))huhu[dem5].pb(a[i]);
        else c[a[i]]=1;
    dem5++;
}
void determine_type(int N)
{
    n=N;
    memset(c,-1,sizeof c);
    per.clear();
    for(int i=0; i<=(n-1)/8; i++)
        v[i].clear();
    for(int i=1; i<=n; i++)
        per.pb(i);
    shuffle(per.begin(),per.end(),rd);
    for(int i=1; i<=n; i++)
        v[(i-1)/8].pb(per[i-1]);
    for(int i=0; i<=(n-1)/8; i++)
        work(v[i]);
    dem5--;
    dem6--;
    for(int i=0; i<=dem5; i++)
        xix(huhu[i]);
    for(int i=1; i<=n; i++)
        if(c[i]==2)s8=i;
    for(int i=0; i<=dem6; i++)
        fhaha(haha[i],s8);
    for(int i=1; i<=n; i++)
        if(c[i]==-1) c[i]=0;
    for(int i=1; i<=n; i++)
    {
        char x;
        if(c[i]==0)x='R';
        if(c[i]==1)x='S';
        if(c[i]==2)x='T';
        // assert(c[i]==color[i]);
        answer_type(i,x);
    }
    for(int i=0; i<=39; i++)
        huhu[i].clear(),haha[i].clear();
    dem5=0;
    dem6=0;
}/*
void phongbeo()
{
    cin>>n;
    for(int j=1; j<=100; j++)
    {
        dem7++;
        for(int i=1; i<=n; i++)
        {
            char x;
            cin>>x;
            if(x=='T')color[i]=2,s9++;
            else if(x=='R')color[i]=0;
            else color[i]=1,s10++;
        }
        determine_type(n);
        dem3=max(dem3,dem4);
        dem4=0;
    }
    cout<<dem3;
}*/

컴파일 시 표준 에러 (stderr) 메시지

toxic.cpp:29:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+16' to '2147483647' [-Woverflow]
   29 | const int inf = 1e16;
      |                 ^~~~

• Subtask 1: 93.25 / 100