Submission #376225

#TimeUsernameProblemLanguageResultExecution timeMemory
376225casperwangLamps (JOI19_lamps)C++14
0 / 100
1074 ms12536 KiB
#include <bits/stdc++.h> #define All(x) x.begin(), x.end() #define pb push_back using namespace std; #define debug(args...) kout("[ " + string(#args) + " ]", args) void kout() { cerr << endl; } template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); } template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; } const int MAXN = 1000000; int n; string a, b; int cnt; int pre[MAXN+1]; vector <int> arr; int ans; signed main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> n; cin >> a >> b; for (int i = 0; i < n; i++) { pre[i] = (i ? pre[i-1] : 0) + (a[i] != b[i]); cnt++; if (i+1==n || b[i] != b[i+1]) { int k = pre[i] - ((i-cnt>=0)?pre[i-cnt]:0); if (!k) arr.pb(0); // +++ else if (k == cnt) arr.pb(1); // --- else if (pre[i]-pre[i-k] == k) arr.pb(2); // ++- else if (pre[i-cnt+k]-((i-cnt>=0)?pre[i-cnt]:0) == k) arr.pb(3); // -++ else arr.pb(4); // other cnt = 0; } } pary(All(arr)); bool flag = false; for (int i = 0; i < arr.size(); i++) { if (arr[i]) { if (arr[i] == 1 || arr[i] == 2) { if (!flag) { if (arr[i] == 2) arr[i] = 1; flag = true; ans++; } } else if (arr[i] == 3) { if (flag) { arr[i] = 1; flag = false; } } } else { if (flag) { flag = false; } } } for (int i : arr) if (i > 1) ans++; cout << ans << '\n'; }

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i = 0; i < arr.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...