Submission #934561

#	Time	Username	Problem	Language	Result	Execution time	Memory
934561		browntoad	Toxic Gene (NOI23_toxic)	C++17	68.95 / 100	20 ms	592 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> T, N, S;
 
    vector<int> qq;
    vector<vector<int>> dai; // match with T at the very end
 
    int tid = -1;
    while(SZ(ids)){
        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){
            dai.pb(tmp);
            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');
            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');
        tid = tmp2[mid];
        FOR(i, mid+1, SZ(tmp2)){
            ids.pb(tmp2[i]);
        }
 
    }
 
    REP(i, SZ(dai)){
        REP(j, SZ(dai[i])){
            REP(k, (1<<j)) qq.pb(dai[i][j]);
        }
        qq.pb(tid);
        ret = query_sample(qq);
        qq.clear();
 
        REP(j, SZ(dai[i])){
            if ((1<<j)&ret){
                answer_type(dai[i][j], 'S');
            }
            else answer_type(dai[i][j], 'R');
        }
    }
}
 
// ~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:74:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |             mid = l+r>>1;
      |                   ~^~
toxic.cpp:72:36: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |         int l = 0, r = SZ(tmp2)-2, mid;
      |                                    ^~~

• Subtask 1: 68.95 / 100