| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 651952 |
2022-10-20T17:15:54 Z |
_martynas |
RLE (BOI06_rle) |
C++11 |
|
582 ms |
100132 KB |
#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};
}
// for(int i = 0; i < k; i++) {
// cerr << A[i].S << " * " << A[i].F << "\n";
// }
// cerr << "-----------------\n";
{
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(x != -1) {
if(event[x].F >= 0) E.PB({event[x].S, event[x].F});
x = event[x].S;
}
reverse(all(E));
int verify = 0;
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 ";
verify += 3;
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) << " ";
verify += 3;
A[i].F -= n;
}
else {
if(A[i].F <= 3) {
cout << A[i].S << " ";
verify++;
A[i].F--;
}
else {
cout << e << " " << A[i].S << " " << min(A[i].F-3, n-1LL) << " ";
verify += 3;
A[i].F -= min(A[i].F-3, n-1LL)+3;
}
}
}
}
return 0;
}
/*
*/
Compilation message
rle.cpp: In function 'int main()':
rle.cpp:221: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]
221 | if(j < E.size() && E[j].F <= i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
15 ms |
3536 KB |
Output is correct |
| 7 |
Correct |
112 ms |
24184 KB |
Output is correct |
| 8 |
Correct |
195 ms |
33528 KB |
Output is correct |
| 9 |
Correct |
321 ms |
65520 KB |
Output is correct |
| 10 |
Correct |
137 ms |
25164 KB |
Output is correct |
| 11 |
Correct |
105 ms |
19436 KB |
Output is correct |
| 12 |
Correct |
192 ms |
41900 KB |
Output is correct |
| 13 |
Correct |
270 ms |
52780 KB |
Output is correct |
| 14 |
Correct |
111 ms |
18076 KB |
Output is correct |
| 15 |
Correct |
45 ms |
9420 KB |
Output is correct |
| 16 |
Correct |
333 ms |
54348 KB |
Output is correct |
| 17 |
Correct |
296 ms |
61928 KB |
Output is correct |
| 18 |
Correct |
315 ms |
61224 KB |
Output is correct |
| 19 |
Correct |
582 ms |
100132 KB |
Output is correct |
| 20 |
Correct |
542 ms |
96600 KB |
Output is correct |
