This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//####################
//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++){
| ~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |