Submission #937745

#	Time	Username	Problem	Language	Result	Execution time	Memory
937745		wojciech_domin2	Lamps (JOI19_lamps)	C++14	47 / 100	1066 ms	129728 KiB

lamp

#include <bits/stdc++.h>
#define pb push_back
#define ins insert
#define fi first
#define se second
#define debug(x) cout<<#x<<" = "<<x<<"\n";

using namespace std;
using ll = long long;
using ld = long double;

template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.fi<<", "<<m.se<<")";
}
 
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}

const int MAX_N = 1000020;
const int INF = 213721372;
char A[MAX_N];
char B[MAX_N];
int dp[MAX_N][2][16];

bitset<MAX_N> a,b;

int main(){
    int N;
    cin>>N;
    for(int i = 1; i <= N; i++){
        cin>>A[i];
    }
    for(int i = 1; i <= N; i++){
        cin>>B[i];
    }
 
    for(int i =1; i <= N; i++){
       
        a[i] = int(A[i]^'0');
        b[i] = int(B[i]^'0');
 
    }
    for(int j = 0; j < MAX_N; j++){
        for(int i = 0; i < 16; i++){
            dp[j][0][i] = INF;
            dp[j][1][i] = INF;
        }
    }
    dp[0][0][0] = 0;
    for(int i = 1; i <= N; i++){
        for(int k = 0; k < 2; k++){
            for(int j = 0; j < 16; j++){
                vector<pair<int,int> > cennik;
                cennik.pb({0,0});
                cennik.pb({1,1});
                cennik.pb({2,1});
                cennik.pb({4,1});
                cennik.pb({5,2});
                cennik.pb({6,2});
                cennik.pb({8,1});
                cennik.pb({9,2});
                cennik.pb({10,2});
                cennik.pb({j,0});
                cennik.pb({j/4,0});
                cennik.pb({(j*4)%16+1,1});
                cennik.pb({(j*4)%16+2,1});
                for(auto t : cennik){
                    dp[i][k][t.fi] = min(dp[i-1][0][j] + k + t.se, dp[i][k][t.fi]);
                    dp[i][k][t.fi] = min(dp[i-1][1][j] + 0 + t.se, dp[i][k][t.fi]);
                }
            }
            
        }
        for(int k = 0; k < 2; k++){
        for(int j = 0; j < 16; j++){
            int R,T;
            R=j/4; T=j%4;
            int kwiatek = T;
            if(kwiatek == 0) kwiatek = R;
            int wart_a = int(A[i]^'0');
            int wart_b = int(B[i]^'0');
            bool ok = false;
            if(kwiatek == 0){
                if((wart_a^k)==wart_b) ok = true;
            }else{
                kwiatek--;
                kwiatek^=k;
                if(wart_b == kwiatek) ok = true;
            }
            if(!ok){
                dp[i][k][j] = INF;
            } 
        }
        }
    }
    int odp = INF;
    for(int i = 0; i < 16; i++){
        odp = min(odp,dp[N][0][i]);
        odp = min(odp,dp[N][1][i]);
    }
  //  debug(dp[4][0][1]);
  //  cout<<dp[9][0][1]<<"\n";
    cout<<odp<<"\n";
   


    return 0;
}

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