oj.uz

Submission #940990

# Submission time Handle Problem Language Result Execution time Memory
940990 2024-03-08T04:30:06 Z LittleFlowers__ Toxic Gene (NOI23_toxic) C++17
9.46154 / 100
 8 ms 504 KB 
#include <bits/stdc++.h>
#include "toxic.h"

using namespace std;

void determine_type (int n) {
  auto query_wrapper = [&](vector<int> q) {
    for (const int& i : q) assert(1 <= i && i <= n);
    int result = query_sample(q);
    assert(result != -1);
    return result;
  };

  vector<bool> answered(n + 1, false);
  auto answer_wrapper = [&](int i, char ch) {
    assert(!answered[i] && 1 <= i && i <= n && (ch == 'S' || ch == 'T' || ch == 'R'));
    answer_type(i, ch);
    answered[i] = true;
    return;
  };

  vector<bool> mark(n + 1);
  int toxic = 0;
  for(int i = 1; i <= n; i++) mark[i] = 0;
  for(int i = 1; i <= n; i++) if (query_wrapper({i}) == 0) {
    answer_wrapper(i, 'T');
    toxic = i;
    mark[i] = 1;
  }
 
  for(int i = 1; i <= n;) {
    int cur = 1;
    vector<int> ask;
    ask.push_back(toxic);
    int j = i;
    while (ask.size() + cur <= 300 && j <= n) {
      for(int k = 1; k <= cur; k++) ask.push_back(j);
      cur *= 2;
      j++;
    }
    int result = query_wrapper(ask);
    for(int k = 0; k < j - i; k++) if (!mark[i + k]) {
      if (result >> k & 1) answer_wrapper(i + k, 'S');
      else answer_wrapper(i + k, 'R');
    }
    i = j;
  }
}

Subtask #1
9.46153846 / 100.0

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