| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 291988 |
2020-09-06T06:39:39 Z |
TAMREF |
None (balkan16_acrobat) |
C++11 |
|
1 ms |
256 KB |
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
void mx(T& t, const U u){
t = max(t, (T)u); }
bool all_is_well(const vector<int>& v){
for(int i = 0, j = 1; j < v.size(); ++i, ++j)
if(v[i] + v[j] == 1) return false;
return true; }
bool unsolvable(const vector<int>& v){
for(const auto x : v) if(x == 2) return false;
return true; }
void conjugate(vector<int>& v){
for(int i = 0; i < v.size(); ++i)
if(v[i] == 1) v[i] = 0;
else if(v[i] == 0) v[i] = 1; }
int cost_remove_all_zeroes(vector<int> v){
const int nr0 = count(begin(v), end(v), 0);
v.erase(remove(begin(v), end(v), 0), end(v));
bool good = (v.front() == 2 || v.back() == 2);
for(int i = 0, j = 1; j < v.size(); ++i, ++j)
if(v[i] == 2 && v[j] == 2) good = true;
return (good ? nr0 : nr0 + 1); }
int X, Y;
template <int delta>
void do_test(int n){
vector<int> v(n);
for(auto& x : v) {
cin >> x;
x = (x == X ? 0 : x == Y ? 1 : 2);
}
if(all_is_well(v)){
cout << 0 << endl;
return; }
if(unsolvable(v)){
cout << -1 << endl;
return; }
set<int> st;
for(const auto x : v) st.insert(x);
assert(st.size() == 3);
int rez = cost_remove_all_zeroes(v);
conjugate(v);
rez = min(rez, cost_remove_all_zeroes(v));
conjugate(v);
static int d[2][2*delta + 10][3][2][2] = {};
memset(d, 0x80, sizeof(d));
d[0][delta][2][0][0] = 0;
int jos = 3, sus = 2 * delta - 3;
// d[i][j][pv][not_ignored0][not_ignored1] = the longest sequence that uses elements upto i
// j = delta + (unsolved_issues - ignored_2s)
for(int i = 0; i <= n; ++i){
memset(d[(i+1)&1], 0x80, sizeof(d[(i+1)&1]));
for(int j = jos; j <= sus; ++j){
for(int pv = 0; pv < 3; ++pv){
for(int i0 = 0; i0 < 2; ++i0){
for(int i1 = 0; i1 < 2; ++i1){
const int vcur = d[i&1][j][pv][i0][i1];
if(vcur < 0) continue;
assert(vcur <= n);
//if(vcur >= 0) cout << i << ' ' << j-delta << ' ' << pv << ' ' << i0 << ' ' << i1 << ' ' << vcur << endl;
//if(vcur == 3) cerr << i << ' ' << j << ' ' << pv << ' ' << i0 << ' '<< i1 << endl;
if(i == n && i0 && i1 && j <= delta){
rez = min(rez, n - (int)vcur); }
if(i == n) continue;
if(v[i] == 2){
mx(d[(i+1)&1][j-1][pv][i0][i1], vcur);
mx(d[(i+1)&1][j][2][i0][i1], vcur + 1); }
else{
mx(d[(i+1)&1][j][pv][i0][i1], vcur);
mx(d[(i+1)&1][j + (pv + v[i] == 1? 1 : 0)][v[i]][i0 || v[i] == 0][i1 || v[i] == 1], vcur + 1); }
} } } } }
cout << rez << endl;
}
int main() {
int t = 1;
while(t--){
int x;
cin >> x >> X >> Y;
if(x <= 45) do_test<20>(x);
else do_test<50>(x);
}
return 0;
}
Compilation message
main.cpp: In function 'bool all_is_well(const std::vector<int>&)':
main.cpp:9:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | for(int i = 0, j = 1; j < v.size(); ++i, ++j)
| ~~^~~~~~~~~~
main.cpp: In function 'void conjugate(std::vector<int>&)':
main.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i = 0; i < v.size(); ++i)
| ~~^~~~~~~~~~
main.cpp: In function 'int cost_remove_all_zeroes(std::vector<int>)':
main.cpp:26:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i = 0, j = 1; j < v.size(); ++i, ++j)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
