Submission #651947

#TimeUsernameProblemLanguageResultExecution timeMemory
651947_martynasRLE (BOI06_rle)C++11
70 / 100
549 ms95372 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using vi = vector<int>; using vl = vector<ll>; const int MOD = 1e9+7; #define F first #define S second #define PB push_back #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } const int MXN = 2e6+5; const ll INF = 1e15; int n, m, k; pll A[MXN]; // {cnt, who} ll cost[MXN]; int last[MXN/19]; ll dp[MXN]; int prev[MXN]; // {do what (-1 - come from left, other - swap to sth), from where (-1 ~ from the beginning)} pii event[MXN+MXN/19]; int MQ[MXN]; int mq; int main() { FASTIO(); // solution for not encoded sequence: cin >> n >> m; int e = 0, b = -1; int which = 0; // 0 - nothing // 1 - e // 2 - ee // 3 - eb for(int i = 0; i < m; i++) { int c; cin >> c; if(which == 3) { if(c == 0) { e = b; } else { A[k++] = {c+3, b}; } which = 0; } else if(which == 2) { A[k++] = {c+1, e}; which = 0; } else if(which == 1) { if(c == e) { which = 2; } else { which = 3; b = c; } } else { if(c == e) { which = 1; } else { A[k++] = {1, c}; } } dp[i] = INF; event[i] = {-100, -100}; } { int j = 0; for(int i = 1; i < k; i++) { if(A[i].S == A[j].S) { A[j].F += A[i].F; } else { j++; A[j] = A[i]; } } k = j+1; } // for(int i = 0; i < k; i++) { // cerr << A[i].S << " * " << A[i].F << "\n"; // } for(int i = 0; i < n; i++) last[i] = -1; auto ceil_div = [](ll x, ll y){ return (x+y-1)/y; }; ll ans = 0; for(int i = 0; i < k; i++) { ll same = 3*ceil_div(A[i].F, n); ll diff = 3*(A[i].F/(n+2)) + min(A[i].F%(n+2), 3LL); ans += diff; cost[i] = same-diff; if(same > diff) { // don't swap since last same number interval int idx = last[A[i].S]; if(idx == -1 && A[i].S == 0) { dp[i] = 0; event[i] = {-1, -1}; } else if(idx != -1) { if(dp[idx]+cost[idx] < dp[i]) { dp[i] = dp[idx]+cost[idx]; event[i] = {-1, idx}; } } // do swap at some place after last same number position if(idx == -1) { if(3LL < dp[i]) { event[i] = {A[i].S, -1}; dp[i] = 3LL; } } else { int l = 0, r = mq-1; while(l < r) { int m = (l+r)/2; if(MQ[m] <= idx) { l = m+1; } else { r = m; } } if(l < mq && MQ[l] > idx) { if(dp[MQ[l]]+3 < dp[i]) { dp[i] = dp[MQ[l]]+3; event[i] = {A[i].S, MQ[l]}; } } } while(mq > 0 && dp[MQ[mq-1]] > dp[i]) { mq--; } MQ[mq++] = i; last[A[i].S] = i; } } ll best = INF; int x = -1; for(int where = 0; where < n; where++) { ll curr = INF; // don't swap since last same number interval int idx = last[where]; if(idx == -1 && where == 0) { curr = 0; event[k+where] = {-1, -1}; } else if(idx != -1) { if(dp[idx]+cost[idx] < curr) { curr = dp[idx]+cost[idx]; event[k+where] = {-1, idx}; } } // do swap at some place after last same number position if(idx == -1) { if(3LL < curr) { event[k+where] = {where, -1}; curr = 3LL; } } else { int l = 0, r = mq-1; while(l < r) { int m = (l+r)/2; if(MQ[m] <= idx) { l = m+1; } else { r = m; } } if(l < mq && MQ[l] > idx) { if(dp[MQ[l]]+3 < curr) { curr = dp[MQ[l]]+3; event[k+where] = {where, MQ[l]}; } } } if(curr < best) { best = curr; x = k+where; } } cerr << ans << " " << best << "\n"; cout << ans+best << "\n"; vector<pii> E; // {where, swap to} while(event[x].S != -1) { if(event[x].F >= 0) E.PB({event[x].S, event[x].F}); x = event[x].S; } reverse(all(E)); e = 0; for(int i = 0, j = 0; i < k; i++) { if(j < E.size() && E[j].F == i) { cout << e << " " << E[j].S << " 0 "; e = E[j].S; j++; } while(A[i].F > 0) { if(A[i].S == e) { cout << e << " " << e << " " << min(A[i].F-1, n-1LL) << " "; A[i].F -= n; } else { if(A[i].F <= 3) { cout << A[i].S << " "; A[i].F--; } else { cout << e << " " << A[i].S << " " << min(A[i].F-3, n-1LL) << " "; A[i].F -= min(A[i].F-3, n-1LL)+3; } } } } return 0; } /* */

Compilation message (stderr)

rle.cpp: In function 'int main()':
rle.cpp:214:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |         if(j < E.size() && E[j].F == i) {
      |            ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...