Submission #648622

#TimeUsernameProblemLanguageResultExecution timeMemory
648622lorenzoferrariMartian DNA (IOI16_dna)C++17
100 / 100
13 ms980 KiB
#include <bits/stdc++.h> using namespace std; bool make_test(string s); unordered_map<string, bool> memo; bool ask(const string& s) { if (memo.find(s) != memo.end()) { return memo[s]; } else { return memo[s] = make_test(s); } } static string nsqrtn(int n, string cur) { constexpr size_t K = 100; string prv = cur; while (cur.size() != n) { if (ask(cur + "1")) { cur = prv = cur + "1"; } else { cur += "0"; } if (cur.size() - prv.size() > K) { if (ask(cur)) { prv = cur; } else { break; } } } while ((int)prv.size() != n && (ask(prv + "0") || ask(prv + "1"))) { if (ask(prv + "0")) { prv += "0"; } else { prv += "1"; } } while ((int)prv.size() != n) { if (ask("0" + prv)) { prv = "0" + prv; } else { prv = "1" + prv; } } return prv; } string analyse(int n, int t) { if (ask(string(200, '0'))) { return nsqrtn(n, string(200, '0')); } int l = 0, r = 200; while (r - l > 1) { int m = (l + r) / 2; if (ask(string(m, '0'))) { l = m; } else { r = m; } } string cur = string(l, '0'); string prv = cur; while ((int)cur.size() != n && (int)(cur.size() - prv.size()) <= l) { if (ask(cur + "1")) { cur = prv = cur + "1"; } else { cur += "0"; } } while (ask(prv + "0")) { prv += "0"; } while ((int)prv.size() != n) { if (ask("0" + prv)) { prv = "0" + prv; } else { prv = "1" + prv; } } return prv; }

Compilation message (stderr)

dna.cpp: In function 'std::string nsqrtn(int, std::string)':
dna.cpp:19:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |     while (cur.size() != n) {
      |            ~~~~~~~~~~~^~~~
grader.cpp: In function 'bool make_test(std::string)':
grader.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for (int i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~
grader.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 1; i <= ss.size(); i++) {
      |                  ~~^~~~~~~~~~~~
grader.cpp:28:13: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   if (pr[i] == p.size()) {
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...