Submission #562477

#TimeUsernameProblemLanguageResultExecution timeMemory
562477aryan12Lamps (JOI19_lamps)C++17
4 / 100
166 ms35652 KiB
#include <bits/stdc++.h> using namespace std; #define int long long mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); int n; string a, b; const int N = 1e6 + 5; int seg[N * 4]; void Build(int l, int r, int pos) { if(l == r) { seg[pos] = a[l] - '0'; return; } int mid = (l + r) >> 1; Build(l, mid, pos * 2); Build(mid + 1, r, pos * 2 + 1); seg[pos] = seg[pos * 2] + seg[pos * 2 + 1]; } int Query(int l, int r, int pos, int ql, int qr) { if(ql <= l && r <= qr) { return seg[pos]; } if(ql > r || l > qr) { return 0; } int mid = (l + r) >> 1; return Query(l, mid, pos * 2, ql, qr) + Query(mid + 1, r, pos * 2 + 1, ql, qr); } void Solve() { cin >> n >> a >> b; Build(0, n - 1, 1); int prev_value = b[0] - '0', start_pos = 0; vector<array<int, 2> > values; // {update, toggle} for(int i = 1; i < n; i++) { if(prev_value != b[i] - '0') { int ans = Query(0, n - 1, 1, start_pos, i - 1); int len = i - 1 - start_pos + 1; if((ans == len && prev_value == 1) || (ans == 0 && prev_value == 0)) // no need to "update" { values.push_back({0, 1}); //0 for set state, 1 (+ 1) for toggle state } else if((ans == len && prev_value == 0) || (ans == 0 && prev_value == 1)) // no need to toggle { values.push_back({1, 0}); } else { values.push_back({1, 1}); } start_pos = i; prev_value = b[i] - '0'; } } int ans = Query(0, n - 1, 1, start_pos, n - 1); int len = n - 1 - start_pos + 1; if((ans == len && prev_value == 1) || (ans == 0 && prev_value == 0)) { values.push_back({0, 1}); } else if((ans == len && prev_value == 0) || (ans == 0 && prev_value == 1)) { values.push_back({1, 0}); } else { values.push_back({1, 1}); } // for(int i = 0; i < values.size(); i++) // { // cout << values[i][0] << " " << values[i][1] << "\n"; // } bool istoggleon = false; ans = 0; int cnt = 0, cnt1 = 0; for(int i = 0; i < values.size(); i++) { if(values[i][0] == 0 && values[i][1] == 1) { istoggleon = false; // ans += values[i][0] = 0 } else if(values[i][0] == 1 && values[i][1] == 0) { if(!istoggleon) ans++; // for opening toggle istoggleon = true; ans = min(ans, ans - cnt + cnt1 / 2 + 1); cnt = 0; cnt1 = 0; } else { ans++; // if(istoggleon) ans += values[i][1]; // else ans += values[i][0]; } if(!istoggleon) { cnt += values[i][0]; cnt1++; } } ans = min(ans, ans - cnt + cnt1 / 2 + 2); // if we toggle the last steps cout << ans << "\n"; } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; return 0; }

Compilation message (stderr)

lamp.cpp: In function 'void Solve()':
lamp.cpp:89:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(int i = 0; i < values.size(); i++)
      |                 ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...