# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
317195 | 2020-10-29T05:18:17 Z | 8e7 | Hidden Sequence (info1cup18_hidden) | C++14 | 9 ms | 412 KB |
#include <iostream> #include <algorithm> #include <utility> #include <vector> #include "grader.h" #define ll long long #define pii pair<int, int> #define maxn 200005 using namespace std; bool poss[1<<10]; bool adj[1<<10][1<<10]; bool Sub (int v, int u, int n, int vs) { int i = 0; for (int x = 0;x < vs;x++) { while (i < n && ((v & (1<<x)) ? 1 : 0) != ((u & (1<<i)) ? 1 : 0)) i ++; if (i == n) return 0; i ++; } return 1; } inline int hbit(int a) { int ret = 0; while (a) { ret++; a >>= 1; } return max(ret, 1); } vector < int > findSequence (int n) { if (n <= 10) { int len = n / 2 + 1; for (int i = 0;i < (1<<len);i++) { int h = hbit(i); //cout << i << ' ' << h << endl; for (int j = 0;j < (1<<n);j++) { if (Sub(i, j, n, len)) { //cout << i << " " << j << endl; adj[i][j] = 1; } } } for (int i = 0;i < (1<<len);i++) { vector<int> v; for (int j = 0;j < len;j++) { if (i & (1<<j)) { v.push_back(1); } else { v.push_back(0); } } if (isSubsequence(v)) { for (int j = 0;j < (1<<n);j++) { if (!adj[i][j]) { poss[j] = true; //cout << i << " " << j << endl; } } } else { for (int j = 0;j < (1<<n);j++) { if (adj[i][j]) { poss[j] = true; //cout << i << " " << j << endl; } } } } for (int i = 0;i < (1<<n);i++) { if (!poss[i]) { vector<int> v; for (int j = 0;j < n;j++) { if (i & (1<<j)) { v.push_back(1); } else { v.push_back(0); } //cout << v[v.size() - 1]; } return v; } } return vector<int>(); } else { int c0 = 0, c1 = 0; for (int i = 1;i <= n;i++) { vector<int> v; for (int j = 0;j < i;j++) v.push_back(0); if (isSubsequence(v)) { c0 = i; } else { break; } } c1 = n -c0; vector<int> ans; for (int i = 1;i <= n;i++) { vector<int> v = ans; v.push_back(0); //cout << min(int(n - v.size()), c1) << endl; int num = n - v.size(); for (int j = 0;j < min(int(num), c1);j++) v.push_back(1); //for (int x = 0;x < v.size();x++) { //cout << v[x]; //} //cout << endl; if (isSubsequence(v)) { ans.push_back(0); } else { ans.push_back(1); c1--; } } return ans; } } /* 5 1 1 1 0 1 12 0 1 0 1 1 1 1 1 0 0 0 0 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 412 KB | Output is correct: Maximum length of a query = 5 |
2 | Correct | 5 ms | 384 KB | Output is correct: Maximum length of a query = 6 |
3 | Correct | 1 ms | 384 KB | Output is correct: Maximum length of a query = 5 |
4 | Correct | 2 ms | 384 KB | Output is correct: Maximum length of a query = 5 |
5 | Correct | 1 ms | 384 KB | Output is correct: Maximum length of a query = 4 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 5 ms | 256 KB | Output is partially correct: Maximum length of a query = 165 |
2 | Partially correct | 6 ms | 256 KB | Output is partially correct: Maximum length of a query = 178 |
3 | Partially correct | 7 ms | 256 KB | Output is partially correct: Maximum length of a query = 190 |
4 | Partially correct | 5 ms | 256 KB | Output is partially correct: Maximum length of a query = 153 |
5 | Partially correct | 7 ms | 256 KB | Output is partially correct: Maximum length of a query = 188 |
6 | Partially correct | 8 ms | 256 KB | Output is partially correct: Maximum length of a query = 172 |
7 | Partially correct | 7 ms | 384 KB | Output is partially correct: Maximum length of a query = 192 |
8 | Partially correct | 5 ms | 384 KB | Output is partially correct: Maximum length of a query = 164 |
9 | Partially correct | 7 ms | 256 KB | Output is partially correct: Maximum length of a query = 200 |
10 | Partially correct | 7 ms | 256 KB | Output is partially correct: Maximum length of a query = 199 |
11 | Partially correct | 7 ms | 384 KB | Output is partially correct: Maximum length of a query = 190 |
12 | Partially correct | 7 ms | 256 KB | Output is partially correct: Maximum length of a query = 199 |
13 | Partially correct | 9 ms | 256 KB | Output is partially correct: Maximum length of a query = 200 |