| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 490851 | keta_tsimakuridze | Hidden Sequence (info1cup18_hidden) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#include "grader.h"
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 200 + 5, mod = 1e9 + 7; // !
int t, dp[N][N], n, a[N];
bool isSubsequence(vector<int> x) {
dp[0][0] = 1;
for(int i = 1; i <= n; i++) {
dp[i][0] = 1;
for(int j = 1; j <= x.size(); j++) {
dp[i][j] = dp[i - 1][j] | (dp[i - 1][j - 1] && a[i] == x[j - 1]);
}
}
return dp[n][x.size()];
}
int get(int t) {
int ans = -1;
vector<int> x;
for(int i = 1; i <= n / 2 + 1; i++) {
x.push_back(t);
if(!isSubsequence(x)) {
ans = i - 1;
break;
}
}
return ans;
}
vector<int> tr(vector<int> x, int t) {
for(int i = 0; i < x.size(); i++) x[i] ^= t;
return x;
}
vector<int> findSequence(int n) {
int cnt0 = -1, cnt1 = 0, t = 0;
cnt0 = get(0);
if(cnt0 == -1) {
t = 1;
cnt0 = get(1);
}
cnt1 = n - cnt0;
int cur = 0; vector<int> ans;
for(int i = 1; i <= cnt1; i++) {
while(true) {
assert(ans.size() <= n);
// 00000 0 11111
if(cur == cnt0) {
ans.push_back(1); break;
}
if(cur + cnt1 - i + 2 <= n/2) { //cout << "++" << i << endl;
vector<int> x;
for(int j = 1; j <= cur + 1; j++) x.push_back(0);
for(int j = 1; j <= cnt1 - i + 1; j++) x.push_back(1);
if(isSubsequence(tr(x, t))) {
cur++; ans.push_back(0);
} else {
ans.push_back(1);
break;
}
}
else {
vector<int> x;
for(int j = 1; j <= i; j++) x.push_back(1);
for(int j = 1; j <= cnt0 - cur; j++) x.push_back(0);
if(isSubsequence(tr(x, t))) {
ans.push_back(1);
break;
}
else {
cur++;
ans.push_back(0);
}
}
}
}
while(cur < cnt0) ans.push_back(0), cur++;
ans = tr(ans, t);
return ans;
}
main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
vector<int> x = findSequence(n);
for(int i = 0; i < x.size(); i++) cout << x[i] <<" ";
}