//#include "grader.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
#define vi vector<int>
const int mxn = 200;
int n;
int b[mxn];
bool isSubsequence(vi v){
int x = 0;
for(int i = 0; i < n && x < v.size(); i++) x += b[i] == v[x];
return x == v.size();
}
vi findSequence(int n){
int x = 0, z = 0, m, k;
vi a, v(n / 2 + 1, x);
x ^= isSubsequence(v);
v.assign(1, x);
while(isSubsequence(v)) v.push_back(x);
k = v.size() - 1;
for(int i = 0; i <= k; i++){
v[i] = !x;
if(isSubsequence(v)) a.push_back(i);
v[i] = x;
}
m = a.size();
vi f, dp[2][m];
f.resize(m);
for(int i = 0; i < 2; i++){
for(int j = 0; j < m; j++){
if(j) dp[i][j].assign(abs(a[j - 1] - i * k) + 1, x);
for(int l = j - 1, y = 1; ~l; l--){
if(l != j - 1) y += abs(a[l + 1] - a[l]);
if(dp[i][l].size() + y + 1 < dp[i][j].size()){
dp[i][j] = dp[i][l];
dp[i][j].push_back(!x);
v.assign(y, x);
dp[i][j].insert(dp[i][j].end(), v.begin(), v.end());
}
}
}
reverse(a.begin(), a.end());
}
reverse(dp[1], dp[1] + m);
for(int j = 0; j < m; j++) reverse(dp[1][j].begin(), dp[1][j].end());
for(int i = 0; i < m; i++){
f[i] = 0;
v = dp[0][i];
v.push_back(!x);
v.insert(v.end(), dp[1][i].begin(), dp[1][i].end());
while(v.size() <= n / 2 + 1 && isSubsequence(v)){
f[i]++;
v.insert(v.begin() + dp[0][i].size(), !x);
}
if(v.size() > n / 2 + 1) f[i] = -1;
else z += f[i];
cout << a[i] << ": " << f[i] << endl;
for(int l = 0; l < 2; l++){
for(int j = 0; j < dp[l][i].size(); j++) cout << dp[l][i][j] << " ";
cout << endl;
}
cout << endl;
}
vi ans;
for(int i = 0; i < m; i++){
if(!~f[i]) f[i] = n - k - z;
v.assign(a[i] - (i ? a[i - 1] : 0), x);
ans.insert(ans.end(), v.begin(), v.end());
v.assign(f[i], !x);
ans.insert(ans.end(), v.begin(), v.end());
}
v.assign(k - a.back(), x);
ans.insert(ans.end(), v.begin(), v.end());
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++) cin >> b[i];
vi v = findSequence(n);
cout << v[0];
for(int i = 1; i < v.size(); i++) cout << " " << v[i];
cout << endl;
return 0;
}
Compilation message
hidden.cpp: In function 'bool isSubsequence(std::vector<int>)':
hidden.cpp:20:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i = 0; i < n && x < v.size(); i++) x += b[i] == v[x];
| ~~^~~~~~~~~~
hidden.cpp:21:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | return x == v.size();
| ~~^~~~~~~~~~~
hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:68:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
68 | while(v.size() <= n / 2 + 1 && isSubsequence(v)){
| ~~~~~~~~~^~~~~~~~~~~~
hidden.cpp:72:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
72 | if(v.size() > n / 2 + 1) f[i] = -1;
| ~~~~~~~~~^~~~~~~~~~~
hidden.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int j = 0; j < dp[l][i].size(); j++) cout << dp[l][i][j] << " ";
| ~~^~~~~~~~~~~~~~~~~
hidden.cpp: In function 'int main()':
hidden.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i = 1; i < v.size(); i++) cout << " " << v[i];
| ~~^~~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:28:26: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
28 | fprintf (fifo_out, "%d\n", ans.size ());
| ~^ ~~~~~~~~~~~
| | |
| int std::vector<int>::size_type {aka long unsigned int}
| %ld
grader.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i=0; i<ans.size () && i < N; i++)
| ~^~~~~~~~~~~~
/tmp/ccBUhNOL.o: In function `isSubsequence(std::vector<int, std::allocator<int> >)':
grader.cpp:(.text+0x0): multiple definition of `isSubsequence(std::vector<int, std::allocator<int> >)'
/tmp/ccC1ZXbv.o:hidden.cpp:(.text+0x0): first defined here
/tmp/ccBUhNOL.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccC1ZXbv.o:hidden.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
