Submission #1163326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163326		Math4Life2020	Lamps (JOI19_lamps)	C++20	10 / 100	259 ms	58208 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N; cin >> N;
    string A,B; cin >> A >> B;
    ll ans = 0;
    vector<bool> va,vb;
    va.push_back(0); vb.push_back(0);
    for (ll i=0;i<N;i++) {
        va.push_back(A[i]=='1');
        vb.push_back(B[i]=='1');
    }
    va.push_back(0); vb.push_back(0);
    set<ll> vda,vdb;
    for (ll i=0;i<(va.size()-1);i++) {
        if (va[i]^va[i+1]) {
            vda.insert(i);
        }
        if (vb[i]^vb[i+1]) {
            vdb.insert(i);
        }
    }
    vda.insert(-1); vdb.insert(-1); 
    vda.insert(2000000); vdb.insert(2000000);
    vector<ll> vcom;
    for (ll x0: vda) {
        if (vdb.find(x0)!=vdb.end()) {
            vcom.push_back(x0);
        }
    }
    ll K = vcom.size();
    ll dp[K]; //double the answer
    dp[0]=0;
    for (ll i=1;i<K;i++) {
        dp[i]=INF;
    }
    for (ll i=1;i<K;i++) {
        for (ll j=max(0LL,i-8);j<i;j++) {
            //cout << "i,j="<<i<<","<<j<<"\n";
            vector<ll> vta,vtb;
            for (auto A0 = vda.upper_bound(vcom[j]);A0!=vda.end() && (*A0)<vcom[i];A0++) {
                vta.push_back((*A0));
            }
            for (auto A0 = vdb.upper_bound(vcom[j]);A0!=vdb.end() && (*A0)<vcom[i];A0++) {
                vtb.push_back(*A0);
            }
            // for (ll x0: vta) {
            //     cout << "vta: "<<x0 <<"\n";
            // }
            // for (ll x0: vtb) {
            //     cout << "vtb: "<<x0 <<"\n";
            // }
            ll dpt = vtb.size()+(vta.size()%2);
            if (vta.size()<=1) {
                //cout << "set: "<<(dp[j]+dpt)<< "\n";
                dp[i]=min(dp[i],dp[j]+dpt);
                continue;
            }
            dpt+=2;
            //cout << "set: "<<(dp[j]+dpt)<< "\n";
            dp[i]=min(dp[i],dp[j]+dpt);
            if (vtb.size()==0) {
                continue;
            }
            ll amin = vtb[0]; ll amax = vtb[vtb.size()-1];
            ll nbtw = 0;
            ll nlb = 0;
            ll nub = 0;
            for (ll x0: vta) {
                if (x0>=amin && x0<=amax) {
                    nbtw++;
                }
                if (x0>=amin) {
                    nlb++;
                }
                if (x0<=amax) {
                    nub++;
                }
            }
            if ((nub == vta.size() || nlb == vta.size())&&vta.size()%2==1) {
                //cout << "f1\n";
                //cout << "set: "<<(dp[j]+dpt-2)<< "\n";
                dp[i]=min(dp[i],dp[j]+dpt-2);
                continue;
            }
            if ((nbtw == (vta.size()) && vta.size()%2==0) || (nbtw >= (vta.size()-1) && vta.size()%2==1)) {
                //cout << "f2\n";
                //cout << "set: "<<(dp[j]+dpt-2)<< "\n";
                dp[i]=min(dp[i],dp[j]+dpt-2);
                continue;
            }
        }
    }
    cout << (dp[K-1]/2);
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49