Submission #955597

#	Time	Username	Problem	Language	Result	Execution time	Memory
955597		ono_de206	Toxic Gene (NOI23_toxic)	C++17	24.26 / 100	6 ms	600 KiB

toxic

#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

//#define int long long

typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

void determine_type(int n) {
    vector<int> type(n + 1, -1);
    int cc = 0;
    auto dfs = [&](auto &self, int l, int r) {
        vector<int> ask(r - l + 1);
        iota(all(ask), l);
        cc++;
        if(query_sample(ask) == r - l + 1) return;
        if(l == r) {
            type[l] = 1;
            // cout << l << '\n';
        } else {
            int m = (l + r) / 2;
            self(self, l, m);
            self(self, m + 1, r);
        }
    };
    int b = 5;
    for(int l = 1, r; l <= n; l += b) {
        r = min(n, l + b - 1);
        dfs(dfs, l, r);
    }
    // cout << endl;
    // cout << " cc here " << cc << endl;
    vector<int> non;
    int samp;
    for(int i = 1; i <= n; i++) {
        if(type[i] == -1) non.pb(i);
        else samp = i;
    }
    for(int l = 0, r; l < non.size(); l = r) {
        r = min((int)non.size(), l + 8);
        vector<int> ask{samp};
        for(int j = l; j < r; j++) {
            int cnt = (1 << (j - l));
            for(int _ = 0; _ < cnt; _++) {
                ask.pb(non[j]);
            }
        }
        int ans = query_sample(ask);
        for(int j = l; j < r; j++) {
            int cnt = (1 << (j - l));
            if(ans & cnt) type[non[j]] = 0;
            else type[non[j]] = 2;
        }
    }
    string str = "STR";
    for(int i = 1; i <= n; i++) {
        answer_type(i, str[type[i]]);
    }
}

Compilation message (stderr)

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:51:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int l = 0, r; l < non.size(); l = r) {
      |                       ~~^~~~~~~~~~~~
toxic.cpp:46:9: warning: 'samp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |     int samp;
      |         ^~~~

• Subtask 1: 24.25882353 / 100