Submission #291988

#	Time	Username	Problem	Language	Result	Execution time	Memory
291988		TAMREF	Acrobat (balkan16_acrobat)	C++11	0 / 100	1 ms	256 KiB

main

#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 (stderr)

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)
      |                           ~~^~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 35
• Subtask 3: 0 / 35