Submission #934783

#	Time	Username	Problem	Language	Result	Execution time	Memory
934783		browntoad	Toxic Gene (NOI23_toxic)	C++17	Compilation error	0 ms	0 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<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;
        while(SZ(tmp) < 8 && ci < SZ(dai)){
            qq.pb(dai[ci]);
            ci++;
        }
        qq.pb(tid);

        ret = query_sample(qq);

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

}

// ~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:57:15: error: 'query_sample' was not declared in this scope
   57 |         ret = query_sample(qq);
      |               ^~~~~~~~~~~~
toxic.cpp:68:17: error: 'answer_type' was not declared in this scope
   68 |                 answer_type(tmp[i], 'S');
      |                 ^~~~~~~~~~~
toxic.cpp:75:13: error: 'answer_type' was not declared in this scope
   75 |             answer_type(tmp2[0], 'T');
      |             ^~~~~~~~~~~
toxic.cpp:82:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |             mid = l+r>>1;
      |                   ~^~
toxic.cpp:98:13: error: 'answer_type' was not declared in this scope
   98 |             answer_type(tmp2[i], 'R');
      |             ^~~~~~~~~~~
toxic.cpp:100:9: error: 'answer_type' was not declared in this scope
  100 |         answer_type(tmp2[mid], 'T');
      |         ^~~~~~~~~~~
toxic.cpp:111:18: error: 'tmp' was not declared in this scope; did you mean 'tm'?
  111 |         while(SZ(tmp) < 8 && ci < SZ(dai)){
      |                  ^~~
toxic.cpp:7:22: note: in definition of macro 'SZ'
    7 | #define SZ(x) (int)((x).size())
      |                      ^
toxic.cpp:117:15: error: 'query_sample' was not declared in this scope
  117 |         ret = query_sample(qq);
      |               ^~~~~~~~~~~~
toxic.cpp:120:29: error: 'answer_type' was not declared in this scope
  120 |             if ((1<<j)&ret) answer_type(qq[j], 'S');
      |                             ^~~~~~~~~~~
toxic.cpp:121:18: error: 'answer_type' was not declared in this scope
  121 |             else answer_type(qq[j], 'R');
      |                  ^~~~~~~~~~~