# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
433522 | 2021-06-20T03:37:28 Z | Lam_lai_cuoc_doi | Hidden Sequence (info1cup18_hidden) | C++17 | 10 ms | 428 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; constexpr bool typetest = 0; constexpr int N = 2e2 + 2; #include "grader.h" bool Check(int a, int b, int c) { vector<int> ans(a, c); while (b--) ans.emplace_back(c ^ 1); return isSubsequence(ans); } vector<int> findSequence(int n) { vector<int> ans; int total(0); // number of zero // count number of zero for (int i = 1; i <= n / 2 + 1; ++i) { if (!Check(i, 0, 0)) break; total = i; } if (total == n / 2 + 1) { total = 0; for (int i = 1; i <= n / 2 + 1; ++i) { if (!Check(i, 0, 1)) break; total = i; } total = n - total; } // Cal ans /* Let i is the bit 0 now we're considering (It means there are i - 1 filled - bits) j is the bit 1 now we're considering (It means there are j - 1 filled - bits) There are 2 cases: - if j + (total - i + 1) <= n / 2 + 1, we could check string (j * '1' + (total - i + 1) * '0') because the bit 0 before we don't need to care - if j + (total - i + 1) > n / 2 <-> n - j - total + i - 1 < n / 2 <-> i + (n - j - total + 1) <= n / 2 + 1: we could checkstring (i * '0' + (n - j - total + 1) * '1') because the string before the (i - 1) - 0 bit is defined so it's only necessary to check string after i - 0 bit */ for (int i = 1, j = 1; i <= total; ++i) // the bit 0 now we're considering { for (; j <= n - total; ++j) { if (j + (total - i + 1) <= n / 2 + 1 ? !Check(j, total - i + 1, 1) : Check(i, n - total - j + 1, 0)) break; ans.emplace_back(1); } ans.emplace_back(0); } while ((int)ans.size() < n) ans.emplace_back(1); return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 200 KB | Output is correct: Maximum length of a query = 5 |
2 | Correct | 1 ms | 200 KB | Output is correct: Maximum length of a query = 6 |
3 | Correct | 1 ms | 200 KB | Output is correct: Maximum length of a query = 5 |
4 | Correct | 1 ms | 200 KB | Output is correct: Maximum length of a query = 5 |
5 | Correct | 1 ms | 200 KB | Output is correct: Maximum length of a query = 4 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 300 KB | Output is correct: Maximum length of a query = 83 |
2 | Correct | 8 ms | 200 KB | Output is correct: Maximum length of a query = 90 |
3 | Correct | 6 ms | 200 KB | Output is correct: Maximum length of a query = 96 |
4 | Correct | 7 ms | 200 KB | Output is correct: Maximum length of a query = 77 |
5 | Correct | 6 ms | 200 KB | Output is correct: Maximum length of a query = 95 |
6 | Correct | 7 ms | 200 KB | Output is correct: Maximum length of a query = 87 |
7 | Correct | 8 ms | 308 KB | Output is correct: Maximum length of a query = 97 |
8 | Correct | 5 ms | 296 KB | Output is correct: Maximum length of a query = 83 |
9 | Correct | 7 ms | 200 KB | Output is correct: Maximum length of a query = 101 |
10 | Correct | 9 ms | 428 KB | Output is correct: Maximum length of a query = 100 |
11 | Correct | 7 ms | 200 KB | Output is correct: Maximum length of a query = 96 |
12 | Correct | 6 ms | 200 KB | Output is correct: Maximum length of a query = 100 |
13 | Correct | 10 ms | 200 KB | Output is correct: Maximum length of a query = 101 |