Submission #1064479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064479		ThylOne	Lamps (JOI19_lamps)	C++14	100 / 100	958 ms	67232 KiB

lamp

//####################
//Lamps
//####################
#include <algorithm>
#include<bits/stdc++.h>
#include <utility>

using namespace std;
string A,B;
const int inf = 2*1e6;

#define pb push_back
#define SET0 1
    #define SET1 2
    #define FLIP 3
void dbg(vector<int> d){
    for(int i:d){
        if(i==SET0)cout<<"set0 ;";
        if(i==SET1)cout<<"set1 ;";
        if(i==FLIP)cout<<"flip ;";

    }
    cout<<endl;
}
bool apply(bool r,int m){
    if(m==SET0)return 0;
    if(m==SET1)return 1;
    if(m==FLIP)return r^1;
    return r;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    int n; cin >> n;
    cin >> A >> B;

    int dp[n+1][4][4];
    for(int a=0;a<=3;a++)for(int b=0;b<=3;b++)dp[n][a][b]=0;
    vector<pair<int,int>> t;
    for(int a=0;a<=3;a++)for(int b=0;b<=3;b++)t.pb(make_pair(a,b));

    for(int pos = n-1;pos>=0;pos--){
        for(int i1 = 0 ; i1<= 3;i1++)
            for(int i2 = 0 ; i2 <= 3;i2++){
                dp[pos][i1][i2] = 2*n+1;
                for(auto &p:t){
                    bool r = A[pos]-'0';
                    r = apply(r,p.first);
                    r = apply(r,p.second);
                    if(r!=(bool)(B[pos]-'0'))continue;
                    int c=2;
                    if(i1==p.second && p.first==0 && i2==0){
                        c=0;
                    }else{
                        if(i1==p.first || p.first==0)c--;
                        if(i2==p.second|| p.second==0)c--;
                    }

                    dp[pos][i1][i2] = min(dp[pos][i1][i2],c+dp[pos+1][p.first][p.second]);
                }
            }
    }
    cout<<dp[0][0][0]<<endl;
    return 0;
};

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