oj.uz

Submission #376553

# Submission time Handle Problem Language Result Execution time Memory
376553 2021-03-11T17:00:50 Z wiwiho Lamps (JOI19_lamps) C++14
0 / 100
 1000 ms 512 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) (((a) + (b) - 1) / (b))
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 1LL << 60;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

struct status{
    vector<vector<ll>> dp;
    status(){
        dp.resize(2, vector<ll>(2, MAX));
    }
    ll& get(int flip, int diff){
        return dp[flip][diff];
    }
    void print(){
        for(int i = 0; i <= 1; i++){
            for(int j = 0; j <= 1; j++) cerr << dp[i][j] << ',';
        }
        cerr << "\n";
    }
};

struct seg{
    vector<vector<ll>> dp;
    seg(){
        dp.resize(2, vector<ll>(3, MAX));
    }
    ll& get(int flip, int all){
        return dp[flip][all];
    }
    ll mn(){
        ll ans = MAX;
        for(int i = 0; i <= 1; i++){
            for(int j = 0; j <= 2; j++) ans = min(ans, dp[i][j]);
        }
    }
    void print(){
        for(int i = 0; i <= 1; i++){
            for(int j = 0; j <= 2; j++) cerr << dp[i][j] << ',';
        }
        cerr << "\n";
    }
};


status transstatus(status from, int v){
    status to;
    for(int flip = 0; flip <= 1; flip++){
        for(int diff = 0; diff <= 1; diff++){
            if(!v && !diff) to.get(0, 0) = min(to.get(0, 0), from.get(flip, diff));
            else to.get(0, 1) = min(to.get(0, 1), from.get(flip, diff));
            if(v && !diff) to.get(1, 0) = min(to.get(1, 0), from.get(flip, diff) + !flip);
            else to.get(1, 1) = min(to.get(1, 1), from.get(flip, diff) + !flip);
        }
    }
    return to;
}

seg transseg(seg from, vector<int>& now){
    seg to;
    for(int flip = 0; flip <= 1; flip++){
        for(int all = 0; all <= 2; all++){
            status st;
            st.get(flip, 0) = from.get(flip, all);
//            cerr << "start " << flip << " " << all << "\n";
//            for(int i : now){
//                st = transstatus(st, i);
////                cerr << "status " << i << " ";
////                st.print();
//            }

            for(int tf = 0; tf <= 1; tf++){
                for(int diff = 0; diff <= 1; diff++){
                    if(!diff){
                        to.get(tf, 0) = min(to.get(tf, 0), st.get(tf, diff));
                    }
                    to.get(tf, 1) = min(to.get(tf, 1), st.get(tf, diff) + 1);
                    if(all == 1){
                        to.get(tf, 2) = min(to.get(tf, 2), st.get(tf, diff) + 1);
                    }
                    if(all == 2){
                        to.get(tf, 1) = min(to.get(tf, 1), st.get(tf, diff));
                    }
                }
            }

        }
    }

    return to;
}

int main(){
    StarBurstStream

    int n;
    cin >> n;

    string a, b;
    cin >> a >> b;

    vector<vector<int>> now;
    int lst = -1;
    for(int i = 0; i < n; i++){
        if(b[i] - '0' != lst) now.eb();
        now.back().eb(b[i] != a[i]);
        lst = b[i] - '0';
    }
//    for(auto& i : now) printv(i, cerr);

    int m = now.size();

    seg s;
    s.get(0, 0) = 0;
    for(int i = 0; i < m; i++){
        s = transseg(s, now[i]);
//        cerr << "seg " << i << " ";
//        s.print();
    }

    cout << s.mn() << "\n";

    return 0;
}

Compilation message

lamp.cpp: In member function 'll seg::mn()':
lamp.cpp:81:5: warning: no return statement in function returning non-void [-Wreturn-type]
   81 |     }
      |     ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -