Submission #950965

#	Time	Username	Problem	Language	Result	Execution time	Memory
950965		browntoad	Toxic Gene (NOI23_toxic)	C++17	100 / 100	22 ms	604 KiB

toxic

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#include "toxic.h"
using namespace std;
/*
int query_sample(vector<int> &a){
    cout<<"? ";
    REP(i, SZ(a)) cout<<a[i]<<' ';
    cout<<endl<<flush;
    int in; cin>>in;
    return in;
}
void answer_type(int a, char c){
    cout<<a<<' '<<c<<endl<<flush;
}
*/



void determine_type(int n){
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    int ret;
    vector<int> ids;
    REP1(i, n) ids.pb(i);
    shuffle(ALL(ids), rng);

    vector<int> qq;
    vector<int> dai; // match with T at the very end

    int tid = -1, cnt = 0;
    while(SZ(ids)){
        if (cnt == 30){
            while(SZ(ids)){
                dai.pb(ids.back());
                ids.pop_back();
            }
            break;
        }
        shuffle(ALL(ids), rng);

        vector<int> tmp;
        int rl = 0; // real id
        while(SZ(tmp) < 8 && SZ(ids) > 0){
            rl++;
            tmp.pb(ids.back());
            ids.pop_back();
        }
        while(SZ(tmp) < 8 && SZ(dai) > 0){
            tmp.pb(dai.back());
            dai.pop_back();
        }

        REP(i, SZ(tmp)){
            REP(j, (1<<i)){
                qq.pb(tmp[i]);
            }
        }
        ret = query_sample(qq);
        qq.clear();

        if (ret == (1<<SZ(tmp))-1){
            REP(j, SZ(tmp)) dai.pb(tmp[j]);
            continue;
        }

        vector<int> tmp2;
        REP(i, SZ(tmp)){
            if (i < rl){
                if ((1<<i)&ret){
                    answer_type(tmp[i], 'S');
                }
                else tmp2.pb(tmp[i]);
            }
            else {
                if ((1<<i)&ret){
                    answer_type(tmp[i], 'S');
                }
                else answer_type(tmp[i], 'R');
            }
        }

        int mid;
        while(SZ(tmp2) > 1){
            mid = SZ(tmp2)/2;

            vector<int> toad;
            REP(i, mid) toad.pb(tmp2[i]);
            while(SZ(toad) < 8 && SZ(dai) > 0){
                toad.pb(dai.back());
                dai.pop_back();
            }


            REP(i, SZ(toad)){
                REP(j, (1<<i)) qq.pb(toad[i]);
            }

            ret = query_sample(qq);
            qq.clear();

            /*FOR(i, mid, SZ(toad)){
                if (ret & (1<<i)){
                    answer_type(toad[i], 'S');
                    ret -= (1<<i);
                }
                else answer_type(toad[i], 'R');
            }
            */

            if (ret != (1<<SZ(toad))-1){ // T exists in the prefix
                FOR(i, mid, SZ(tmp2)){
                    ids.pb(tmp2[i]);
                }
                while(SZ(tmp2) > mid) tmp2.pop_back();
                FOR(i, mid, SZ(toad)){
                    if (ret & (1<<i)){
                        answer_type(toad[i], 'S');
                        ret -= (1<<i);
                    }
                    else answer_type(toad[i], 'R');
              	}
            }
            else {
                REP(i, mid){
                    answer_type(tmp2[i], 'R');
                }
                tmp2.erase(tmp2.begin(), tmp2.begin()+mid);
              	FOR(i, mid, SZ(toad)){
                    dai.pb(toad[i]);
            	}
            }
        }

        // use tmp2 from now on
        assert(SZ(tmp2) == 1);
        tid = tmp2[0];
        answer_type(tmp2[0], 'T');
        cnt++;


        /*REP(i, mid){
            answer_type(tmp2[i], 'R');
        }
        answer_type(tmp2[mid], 'T');
        cnt++;
        tid = tmp2[mid];
        FOR(i, mid+1, SZ(tmp2)){
            ids.pb(tmp2[i]);
        }
        */

    }

    for (int i = 0; i < SZ(dai); i += 8){
        int ci = i;
        vector<int> tmp;
        while(SZ(tmp) < 8 && ci < SZ(dai)){
            REP(j, (1<<(ci-i))){
                qq.pb(dai[ci]);
            }
            tmp.pb(dai[ci]);
            ci++;
        }
        qq.pb(tid);

        ret = query_sample(qq);
        qq.clear();

        REP(j, SZ(tmp)){
            if ((1<<j)&ret) answer_type(tmp[j], 'S');
            else answer_type(tmp[j], 'R');
        }
    }

}
/*
signed main(){
    determine_type(4);
}
*/


// ~270/x * (log2(x)+1) + 30*(log2(x)+1)

// ~270/x + (log2(x)+1)*30 - random chances to deduct more from top + remaining ranges need matching

• Subtask 1: 100 / 100