Submission #936913

#	Time	Username	Problem	Language	Result	Execution time	Memory
936913		vjudge1	Toxic Gene (NOI23_toxic)	C++17	68.95 / 100	8 ms	540 KiB

toxic

#include "toxic.h"
#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())
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> T, N, S;
 
    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;
        while(SZ(tmp) < 8 && SZ(ids) > 0){
            tmp.pb(ids.back());
            ids.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 ((1<<i)&ret){
                answer_type(tmp[i], 'S');
            }
            else tmp2.pb(tmp[i]);
        }
        // use tmp2 from now on
        if (SZ(tmp2) == 1){
            tid = tmp2[0];
            answer_type(tmp2[0], 'T');
            cnt++;
            continue;
        }
 
        int l = 0, r = SZ(tmp2)-2, mid;
        while(l <= r){
            mid = l+r>>1;
 
            REP(i, mid+1) qq.pb(tmp2[i]);
            ret = query_sample(qq);
            qq.clear();
 
            if (l == r){
                mid = l+(ret != 0);
                break;
            }
 
            if (ret == 0) r = mid-1;
            else l = mid+1;
        }
 
        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

Compilation message (stderr)

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:83:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |             mid = l+r>>1;
      |                   ~^~
toxic.cpp:81:36: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |         int l = 0, r = SZ(tmp2)-2, mid;
      |                                    ^~~

• Subtask 1: 68.95 / 100