Submission #1054187

#TimeUsernameProblemLanguageResultExecution timeMemory
1054187chaoslongLamps (JOI19_lamps)C++14
100 / 100
44 ms33732 KiB
// Calm down. // Think three times, code twice. #include "bits/stdc++.h" #define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a) #define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);) #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a) #define st first #define nd second #define ll long long #define ull unsigned long long #define pii pair <int,int> #define pll pair <ll,ll> #define piii pair <int,pii> #define vi vector <int> #define pb push_back #define mp make_pair #define all(x) begin(x),end(x) #define mask(i) (1LL << (i)) #define bit(x, i) (((x) >> (i)) & 1) #define bp __builtin_popcountll #define file "test" using namespace std; const int N = 1e6 + 5; const int mod = 1e9 + 7; // 998244353 const ll oo = 1e18; int n; int a[N], b[N]; int dp[N][3][2]; void to_nho_cau() { cin >> n; int dem1 = 0, dem0 = 0; forr(i, 1, n) { char x; cin >> x; a[i] = (x == '1') ? 1: 0; } forr(i, 1, n) { char x; cin >> x; b[i] = (x == '1') ? 1: 0; } memset(dp, 0x3f, sizeof dp); dp[0][0][0] = 0; forr(i, 1, n) { forr(j, 0, 2) { forr(k, 0, 1) { //j = 0 là giữ nguyên giá trị ban đầu // = 1 là chuyển thành 0 // = 2 là chuyển thành 1 //k = 0 nghĩa là đảo tại vị trí này int val = a[i]; if(j == 1) val = 0; if(j == 2) val = 1; if(k == 1) val ^= 1; if(val != b[i]) continue; forr(j2, 0, 2) { forr(k2, 0, 1) { dp[i][j][k] = min(dp[i][j][k], dp[i-1][j2][k2] + (j > 0 && j != j2) + (k > 0 && k != k2)); } } } } } int ans = mod; forr(j, 0, 2) { forr(k, 0, 1) { ans = min(ans, dp[n][j][k]); } } cout << ans << "\n"; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); #ifdef LOCAL freopen(file".inp","r",stdin); freopen(file".out","w",stdout); #endif int t = 1; //cin >> t; while(t--) to_nho_cau(); } /* 1.self check: 2.long long 3.size of array 4.code for testing 5.initializing 6.modulo number */ /** ∧__∧ (`•ω• )づ__∧ (つ  /( •ω•。) しーJ (nnノ) pat pat **/ /** /\_/\ * (= ._.) * / >☕ \>💻 **/ /** ・*・ ∧,,∧ ∧_∧ ・*・ '.  ( 。・ω・)(・ω・。 )  .'  '・ | つ♥と |.・' *'***** '* **/

Compilation message (stderr)

lamp.cpp:98:9: warning: "/*" within comment [-Wcomment]
   98 | /**  /\_/\
      |          
lamp.cpp: In function 'void to_nho_cau()':
lamp.cpp:34:9: warning: unused variable 'dem1' [-Wunused-variable]
   34 |     int dem1 = 0, dem0 = 0;
      |         ^~~~
lamp.cpp:34:19: warning: unused variable 'dem0' [-Wunused-variable]
   34 |     int dem1 = 0, dem0 = 0;
      |                   ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...