Submission #919116

#	Time	Username	Problem	Language	Result	Execution time	Memory
919116		ThylOne	Lamps (JOI19_lamps)	C++14	10 / 100	738 ms	161268 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
const int maxiN = 1000000;
int n;
bool a[maxiN],b[maxiN];
const int RIEN = 0;
const int ONE = 1;
const int ZERO = 2;
const int FLIP = 3;
bool apply(bool v,int s){
    if(s==ONE)return 1;
    if(s==ZERO)return 0;
    if(s==FLIP)return !v;
    if(s==RIEN)return v;
}
int dp[maxiN][4][4];
int solve(int pos,int s1,int s2){
    
    if(pos==n)return 0;
    if(dp[pos][s1][s2]!=-1)return dp[pos][s1][s2];
    int ans = n+1;
    //On change que le dernier inter
    
    for(int i=RIEN;i<=FLIP;i++){
        bool p = apply(apply(a[pos],s1),i);
        if(p==b[pos] && i!=s1){
            ans = min(ans,((s2==i || i==RIEN)?0:1)+solve(pos+1,s1,i));
        }
    }
    //On retire le premier
    for(int i=RIEN;i<=FLIP;i++){
        bool p = apply(apply(a[pos],s2),i);
        if(p==b[pos] && i!=s2){
            ans = min(ans,((i==RIEN)?0:1)+solve(pos+1,s2,i));
        }
    }
    //On retire tout
    for(int i = RIEN+1;i<=FLIP;i++){
        for(int j=RIEN;j<=FLIP;j++){
            bool p = apply(apply(a[pos],i),j);
            if(p==b[pos]){
                int malus = (i!=RIEN) + (j!=RIEN);
                ans = min(ans,malus+solve(pos+1,i,j));
            }
        }
    }
    if(a[pos]==b[pos]){
        ans = min(ans,solve(pos+1,RIEN,RIEN));
    }
    return dp[pos][s1][s2]=ans;
}
signed main(){
    string f,t;
    cin>>n;
    cin>>f>>t;
    for(int i = 0;i<n;i++){
        a[i] = (f[i]=='1');
        b[i] = (t[i]=='1');
    }
    for(int i = 0;i<maxiN;i++){
        for(int c=0;c<4;c++){
            for(int g=0;g<4;g++){
                dp[i][c][g]=-1;
            }
        }
    }
    cout<<solve(0,RIEN,RIEN)<<endl;
    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'bool apply(bool, int)':
lamp.cpp:15:1: warning: control reaches end of non-void function [-Wreturn-type]
   15 | }
      | ^

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