Submission #941043

#TimeUsernameProblemLanguageResultExecution timeMemory
941043socpiteToxic Gene (NOI23_toxic)C++17
28.14 / 100
9 ms600 KiB
#include<bits/stdc++.h> #include"toxic.h" using namespace std; mt19937 rng(69420); int query_sample(vector<int> species); int h[301]; int shuffled_query(vector<int> speices){ for(auto &v: speices)v = h[v]; return query_sample(speices); } void shuffled_answer(int x, char c){ answer_type(h[x], c); } void determine_type(int n){ int l = 1, r = n; iota(h+1, h+n+1, 1); // shuffle(h+1, h+n+1, rng); vector<int> vec(n); vector<bool> bad(n+1, 0); vector<bool> done(n+1, 0); iota(vec.begin(), vec.end(), 1); while(l < r){ int mid = (l+r)>>1; int tmp = shuffled_query(vector<int>(vec.begin() + l - 1, vec.begin() + mid)); if(tmp != mid - l + 1)r = mid; else l = mid+1; } vec.erase(vec.begin() + l - 1); shuffled_answer(l, 'T'); // vector<int> missing; int tcnt = 0; while(!vec.empty()){ // shuffle(vec.begin(), vec.end(), rng); vector<int> sampling; vector<int> species; vector<int> missing; for(int i = 0; i < min<int>(8, vec.size()); i++){ sampling.push_back(vec[i]); for(int _ = 0; _ < (1<<i); _++)species.push_back(vec[i]); } for(int i = 0; i < sampling.size(); i++)vec.erase(vec.begin()); bool all_bad = 1; for(auto v: sampling)if(!bad[v])all_bad = 0; if(all_bad && tcnt == 30){ for(auto v: sampling)shuffled_answer(v, 'R'); } int tot1 = shuffled_query(species); if(tot1 == species.size()){ species.push_back(l); if(all_bad || tcnt == 30){ for(auto v: sampling)shuffled_answer(v, 'R'); continue; } int tot2 = shuffled_query(species); for(int i = 0; i < sampling.size(); i++){ if((tot1&tot2)&(1<<i))shuffled_answer(sampling[i], 'S'); else shuffled_answer(sampling[i], 'R'); } } else { shuffle(missing.begin(), missing.end(), rng); for(int i = 0; i < sampling.size(); i++){ if(tot1&(1<<i)){ shuffled_answer(sampling[i], 'S'); } else missing.push_back(sampling[i]); } int i; for(i = 0; i + 1 < missing.size(); i++){ if(!shuffled_query({missing[i]})){ shuffled_answer(missing[i], 'T'); for(int j = i+1; j < missing.size(); j++)vec.push_back(missing[j]); break; } shuffled_answer(missing[i], 'R'); } if(i == missing.size() - 1)shuffled_answer(missing[i], 'T'); } } }

Compilation message (stderr)

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i = 0; i < sampling.size(); i++)vec.erase(vec.begin());
      |                  ~~^~~~~~~~~~~~~~~~~
toxic.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if(tot1 == species.size()){
      |            ~~~~~^~~~~~~~~~~~~~~~~
toxic.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for(int i = 0; i < sampling.size(); i++){
      |                            ~~^~~~~~~~~~~~~~~~~
toxic.cpp:68:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int i = 0; i < sampling.size(); i++){
      |                            ~~^~~~~~~~~~~~~~~~~
toxic.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    for(i = 0; i + 1 < missing.size(); i++){
      |               ~~~~~~^~~~~~~~~~~~~~~~
toxic.cpp:78:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |      for(int j = i+1; j < missing.size(); j++)vec.push_back(missing[j]);
      |                       ~~^~~~~~~~~~~~~~~~
toxic.cpp:83:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    if(i == missing.size() - 1)shuffled_answer(missing[i], 'T');
      |       ~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...