#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 < 64; 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/4,0});
cennik.pb({(j<<2)%16+1,1});
cennik.pb({(j<<2)%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 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]);
}
cout<<odp<<"\n";
return 0;
}
Compilation message
lamp.cpp: In function 'int main()':
lamp.cpp:54:25: warning: iteration 16 invokes undefined behavior [-Waggressive-loop-optimizations]
54 | dp[j][0][i] = INF;
| ~~~~~~~~~~~~^~~~~
lamp.cpp:53:26: note: within this loop
53 | for(int i = 0; i < 64; i++){
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
127572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
127572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
127568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
127572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
