Submission #955597

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
955597	2024-03-31T05:07:45 Z	ono_de206	Toxic Gene (NOI23_toxic)	C++17	24.2588 / 100	6 ms	600 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Partially correct	4 ms	348 KB	Partially correct
3	Partially correct	4 ms	348 KB	Partially correct
4	Partially correct	4 ms	508 KB	Partially correct
5	Partially correct	4 ms	348 KB	Partially correct
6	Partially correct	4 ms	496 KB	Partially correct
7	Partially correct	4 ms	348 KB	Partially correct
8	Partially correct	4 ms	348 KB	Partially correct
9	Partially correct	6 ms	348 KB	Partially correct
10	Partially correct	4 ms	348 KB	Partially correct
11	Partially correct	4 ms	500 KB	Partially correct
12	Partially correct	4 ms	344 KB	Partially correct
13	Partially correct	4 ms	348 KB	Partially correct
14	Partially correct	4 ms	348 KB	Partially correct
15	Partially correct	4 ms	344 KB	Partially correct
16	Partially correct	4 ms	348 KB	Partially correct
17	Partially correct	4 ms	348 KB	Partially correct
18	Partially correct	4 ms	348 KB	Partially correct
19	Partially correct	4 ms	348 KB	Partially correct
20	Partially correct	4 ms	344 KB	Partially correct
21	Partially correct	4 ms	348 KB	Partially correct
22	Partially correct	4 ms	344 KB	Partially correct
23	Partially correct	4 ms	348 KB	Partially correct
24	Correct	4 ms	348 KB	Output is correct
25	Correct	4 ms	348 KB	Output is correct
26	Correct	4 ms	348 KB	Output is correct
27	Correct	4 ms	344 KB	Output is correct
28	Correct	6 ms	352 KB	Output is correct
29	Correct	4 ms	600 KB	Output is correct
30	Partially correct	4 ms	348 KB	Partially correct
31	Correct	4 ms	344 KB	Output is correct
32	Correct	4 ms	344 KB	Output is correct
33	Correct	4 ms	500 KB	Output is correct
34	Partially correct	4 ms	344 KB	Partially correct
35	Partially correct	4 ms	348 KB	Partially correct
36	Partially correct	1 ms	348 KB	Partially correct