Submission #1064431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064431		ThylOne	Lamps (JOI19_lamps)	C++14	0 / 100	1067 ms	98392 KiB

lamp

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

using namespace std;
string A,B;
const int inf = 2*1e6;
#define SET0 0
#define SET1 1
#define FLIP 2
#define pb push_back
vector<int> desciption(int s0, int s1, int flip,int order_set){
    vector<int> d;
    if(s0)d.pb(SET0);
    if(s1)d.pb(SET1);
    if(order_set==0 && d.size()==2)swap(d[0],d[1]);

    if(flip){
        if(flip&1){
            d.pb(FLIP);
        }else{
            reverse(d.begin(),d.end());
            d.pb(FLIP);
            reverse(d.begin(),d.end());
        }
    }
    return d;
}

int tcost(vector<int> a,vector<int> b){
    int cost = b.size();
    for(int i = 0;i<min(b.size(),a.size());i++){
        if(b[i]!=a[i])break;
        cost--;
    }
    return cost;
}
bool apply(vector<int> d,bool v){

    for(int i:d){
        if(i==SET0)v=0;
        if(i==SET1)v=1;
        if(i==FLIP)v^=1;
    }
    return v;
}

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;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    int n; cin >> n;
    cin >> A >> B;
    int dp[n+1][2][2][3][2];

    for(int s1=0;(int)s1<2;s1++)
        for(int s0=0;s0<2;s0++)
            for(int p=0;p<2;p++)
                for(int f=0;f<3;f++){
                   dp[n][s0][s1][f][p]=0;
                }
    for(int pos = n-1;pos>=0;pos--){
        for(int s1=0;(int)s1<2;s1++)
            for(int s0=0;s0<2;s0++)
                for(int p=0;p<2;p++)
                    for(int f=0;f<3;f++){
                        dp[pos][s0][s1][f][p] = 2*n+1;
                        for(int ts1=0;(int)ts1<2;ts1++)
                            for(int ts0=0;ts0<2;ts0++)
                                for(int tp=0;tp<2;tp++)
                                    for(int tf=0;tf<3;tf++){
                                        vector<int> a = desciption(s0, s1, f,p);
                                        vector<int> b = desciption(ts0, ts1, tf,tp);
                                        
                                        if(apply(b,(bool)(A[pos]-'0'))!=(bool)(B[pos]-'0'))
                                            continue;
                                        int c = tcost(a,b);
                                        int re = c+dp[pos+1][ts0][ts1][tf][tp];
                                        dp[pos][s0][s1][f][p] = min(dp[pos][s0][s1][f][p],re);
                                    }
                    }
                        
                      
    }
    cout<<dp[0][0][0][0][0]<<endl;
    
    
    return 0;
};

Compilation message (stderr)

lamp.cpp: In function 'int tcost(std::vector<int>, std::vector<int>)':
lamp.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   34 |     for(int i = 0;i<min(b.size(),a.size());i++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~

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