| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1104113 |
2024-10-22T20:10:20 Z |
Kirill22 |
RLE (BOI06_rle) |
C++17 |
|
1221 ms |
93220 KB |
#include "bits/stdc++.h"
using namespace std;
mt19937 gen(22);
void solve() {
int m, n;
m = gen() % 200000 + 2;
n = gen() % 300000 + 1;
cin >> m >> n;
vector<int> a;
if (1) {
a.resize(n);
for (int i = 0; i < n; i++) {
// a[i] = gen() % (m - 1) + 1;
cin >> a[i];
}
} else {
cout << "start" << endl;
for (int i = 0, cur = 0; i < n; i++) {
int t = gen() % 4;
int val = gen() % m;
while (val == cur) val = gen() % m;
if (t == 0) {
a.push_back(val);
} else if (t == 1) {
a.push_back(cur); a.push_back(cur); a.push_back(gen() % m);
} else if (t == 2) {
a.push_back(cur); a.push_back(val); a.push_back(0);
cur = val;
} else {
a.push_back(cur); a.push_back(val); a.push_back(gen() % (m - 1) + 1);
}
}
cout << "end" << endl;
n = (int) a.size();
}
if (0) {
// cout << m << " " << n << endl;
// for (auto &x: a) {
// cout << x << " ";
// }
// cout << endl;
}
vector<pair<int, long long>> b;
auto add = [&] (int x, int c) {
if (!b.empty() && b.back().first == x) {
b.back().second += c;
} else {
b.push_back({x, c});
}
};
for (int l = 0, t = 0; l < n; ) {
if (a[l] != t) {
add(a[l], 1);
l++;
} else if (a[l] == a[l + 1]) {
add(a[l], a[l + 2] + 1);
l += 3;
} else if (a[l + 2] == 0) {
t = a[l + 1];
l += 3;
} else {
add(a[l + 1], a[l + 2] + 3);
l += 3;
}
}
set<pair<int, int>> st;
vector<int> dp(m, 3);
int w = 0;
dp[0] = 0;
for (int i = 0; i < m; i++) {
st.insert({dp[i], i});
}
vector<int> mem(b.size());
for (int i = 0; i < (int) b.size(); i++) {
auto [x, len] = b[i];
// 4 ... m + 2
int op = (int) 1e9;
for (int d = 0; d <= min(len, 3ll); d++) {
int k = (len - d + m + 1) / (m + 2);
if (len - d >= k * 4) {
op = min(op, k * 3 + d);
}
}
int val1 = dp[x] + w + (len + m - 1) / m * 3;
auto it = st.begin();
if (it->second == x) {
it = next(it);
}
int val2 = it->first + w + op + 3;
st.erase({dp[x], x});
w += op;
dp[x] = min(val1, val2) - w;
mem[i] = val1 < val2 ? x : it->second;
st.insert({dp[x], x});
// if (st.begin()->first + w < 0) {
// cout << i << " " << len << " " << m << " " << val1 << " " << val2 << endl;
// exit(0);
// }
}
// cout << "F" << endl << endl << endl;
int answer = st.begin()->first + w, last = st.begin()->second;
// cout << answer << endl;
vector<int> ans;
for (int i = (int) b.size() - 1; i >= 0; i--) {
auto [x, len] = b[i];
if (last != x) {
pair<int, int> op = {(int) 1e9, -1};
for (int d = 0; d <= min(len, 3ll); d++) {
int k = (len - d + m + 1) / (m + 2);
if (len - d >= k * 4) {
op = min(op, {k * 3 + d, d});
}
}
while (op.second) {
ans.push_back(x);
len--;
op.first--;
op.second--;
}
int k = op.first / 3;
while (k) {
// (len - cur) >= (k - 1) * 4
int cur = min((long long) m + 2, len - (k - 1) * 4);
ans.push_back(cur - 3);
ans.push_back(x);
ans.push_back(last);
k--;
len -= cur;
}
} else if (mem[i] != x) {
last = mem[i];
ans.push_back(0);
ans.push_back(x);
ans.push_back(last);
pair<int, int> op = {(int) 1e9, -1};
for (int d = 0; d <= min(len, 3ll); d++) {
int k = (len - d + m + 1) / (m + 2);
if (len - d >= k * 4) {
op = min(op, {k * 3 + d, d});
}
}
while (op.second) {
ans.push_back(x);
len--;
op.first--;
op.second--;
}
int k = op.first / 3;
while (k) {
// (len - cur) >= (k - 1) * 4
int cur = min((long long) m + 2, len - (k - 1) * 4);
ans.push_back(cur - 3);
ans.push_back(x);
ans.push_back(last);
k--;
len -= cur;
}
} else {
int k = (len + m - 1) / m;
while (k) {
int cur = min((long long) m, len);
ans.push_back(cur - 1);
ans.push_back(x);
ans.push_back(x);
k--;
len -= cur;
}
}
}
if (last) {
ans.push_back(0);
ans.push_back(last);
ans.push_back(0);
}
assert(answer == (int) ans.size());
std::reverse(ans.begin(), ans.end());
cout << answer << '\n';
for (auto& x : ans) {
cout << x << " ";
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
13 ms |
2128 KB |
Output is correct |
| 7 |
Correct |
87 ms |
13288 KB |
Output is correct |
| 8 |
Correct |
112 ms |
19520 KB |
Output is correct |
| 9 |
Correct |
210 ms |
44724 KB |
Output is correct |
| 10 |
Correct |
79 ms |
12868 KB |
Output is correct |
| 11 |
Correct |
69 ms |
12864 KB |
Output is correct |
| 12 |
Correct |
195 ms |
32416 KB |
Output is correct |
| 13 |
Correct |
177 ms |
30344 KB |
Output is correct |
| 14 |
Correct |
104 ms |
14524 KB |
Output is correct |
| 15 |
Correct |
55 ms |
7848 KB |
Output is correct |
| 16 |
Correct |
197 ms |
32424 KB |
Output is correct |
| 17 |
Correct |
251 ms |
37928 KB |
Output is correct |
| 18 |
Correct |
316 ms |
43048 KB |
Output is correct |
| 19 |
Correct |
1221 ms |
93220 KB |
Output is correct |
| 20 |
Correct |
1075 ms |
93212 KB |
Output is correct |
