Submission #1164138

#TimeUsernameProblemLanguageResultExecution timeMemory
1164138canhnam357Combo (IOI18_combo)C++20
100 / 100
8 ms564 KiB
#include <bits/stdc++.h> #include "combo.h" using namespace std; // string S = "ABXYY"; // // z[i] = length of longest common prefix of s[0..N] and s[i..N] // vector<int> zfunc(const string& s) { // int n = (int)s.length(); // vector<int> z(n); // z[0] = n; // for (int i = 1, l = 0, r = 0; i < n; ++i) { // if (i <= r) // z[i] = min(r - i + 1, z[i - l]); // while (i + z[i] < n && s[z[i]] == s[i + z[i]]) // ++z[i]; // if (i + z[i] - 1 > r) // l = i, r = i + z[i] - 1; // } // return z; // } // int press(string p) // { // string s = S + "#" + p; // vector<int> z = zfunc(s); // return *max_element(z.begin() + (int)(S.size()), z.end()); // } auto seed = chrono::high_resolution_clock::now().time_since_epoch().count(); mt19937_64 mt(seed); long long get_random(long long l, long long r, bool non_zero = 0) { assert(l <= r); long long res; while (true) { res = mt() % (r - l + 1) + l; if (non_zero && !res) continue; break; } return res; } string guess_sequence(int N) { int asked = 0; string chars = "ABXY"; string t = ""; if (press(chars.substr(0, 2))) { if (press(chars.substr(0, 1))) { t += chars[0]; chars.erase(0, 1); } else { t += chars[1]; chars.erase(1, 1); } } else { if (press(chars.substr(2, 1))) { t += chars[2]; chars.erase(2, 1); } else { t += chars[3]; chars.erase(3, 1); } } if (N == 1) return t; asked += 2; for (int i = 2; i < N; i++) { string a = t; a += chars[0]; string b = t; b += chars[1]; string s = a; for (char c : chars) { b += c; s += b; b.pop_back(); } asked++; int k = press(s); if (k == i) t += chars[0]; else if (k == i + 1) t += chars[1]; else t += chars[2]; } if (press(t + chars.substr(0, 1)) == N) { t += chars[0]; } else if (press(t + chars.substr(1, 1)) == N) { t += chars[1]; } else t += chars[2]; //cout << "ASKED " << asked << '\n'; return t; } // int main() // { // cout << guess_sequence(S.size()); // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...