제출 #937739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937739		wojciech_domin2	Lamps (JOI19_lamps)	C++14	0 / 100	83 ms	127572 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 < 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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++){
      |                        ~~^~~~

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