| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 698105 |
2023-02-12T10:48:38 Z |
finn__ |
RLE (BOI06_rle) |
C++17 |
|
994 ms |
135544 KB |
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t n, m;
cin >> n >> m;
vector<pair<unsigned, uint64_t>> seq;
unsigned e = 0;
for (size_t i = 0; i < m; i++)
{
unsigned x;
cin >> x;
if (x == e)
{
i += 2;
unsigned y, z;
cin >> y >> z;
if (y == e)
{ // Repeat e.
if (!seq.empty() && seq.back().first == x)
seq.back().second += z + 1;
else
seq.emplace_back(x, z + 1);
}
else
{
if (z)
{ // Repeat y.
if (!seq.empty() && seq.back().first == y)
seq.back().second += z + 3;
else
seq.emplace_back(y, z + 3);
}
else
e = y;
}
}
else
{
if (!seq.empty() && seq.back().first == x)
seq.back().second++;
else
seq.emplace_back(x, 1);
}
}
uint64_t cost = 0;
vector<uint64_t> additional_cost(seq.size());
for (size_t i = 0; i < seq.size(); i++)
{
auto const &[l, a] = seq[i];
uint64_t c;
if (a <= 3)
c = a;
else
c = 3 * (a / (n + 3) + 1);
additional_cost[i] = 3 * (a / (n + 1) + 1) - c;
cost += c;
}
priority_queue<pair<uint64_t, unsigned>, vector<pair<uint64_t, unsigned>>, greater<pair<uint64_t, unsigned>>> q;
vector<uint64_t> dp(n);
vector<vector<unsigned>> prev_letter(n), position(n);
q.emplace(0, 0);
dp[0] = 0;
for (unsigned i = 1; i < n; i++)
q.emplace(3, i), dp[i] = 3;
for (size_t i = 0; i < seq.size(); i++)
{
unsigned const l = seq[i].first;
while (dp[q.top().second] != q.top().first || q.top().second == l)
q.pop();
if (q.top().first + 3 < dp[l] + additional_cost[i])
{
dp[l] = q.top().first + 3;
prev_letter[l].push_back(q.top().second);
position[l].push_back(i); // Means switch directly after i.
}
else
dp[l] += additional_cost[i];
q.emplace(dp[l], l);
}
while (q.top().first != dp[q.top().second])
q.pop();
cout << cost + q.top().first << '\n';
vector<unsigned> code, switches, switch_positions;
unsigned x = q.top().second, p = seq.size();
while (1)
{
size_t i = lower_bound(position[x].begin(), position[x].end(), p) - position[x].begin();
if (!i)
break;
unsigned y = prev_letter[x][i - 1];
p = position[x][i - 1];
switches.push_back(x);
switch_positions.push_back(p);
x = y;
}
reverse(switches.begin(), switches.end());
reverse(switch_positions.begin(), switch_positions.end());
e = 0;
size_t j = 0;
for (int64_t i = 0; i < seq.size(); i++)
{
if (j < switches.size() && switch_positions[j] < i)
{
code.push_back(e);
code.push_back(switches[j]);
code.push_back(0);
e = switches[j];
j++;
}
if (seq[i].second <= 3)
{
if (seq[i].first != e)
{
for (size_t k = 0; k < seq[i].second; k++)
code.push_back(seq[i].first);
}
else
{
code.push_back(e);
code.push_back(e);
code.push_back(seq[i].second - 1);
}
}
else
{
if (seq[i].first != e)
{
while (seq[i].second > 3)
{
code.push_back(e);
code.push_back(seq[i].first);
code.push_back(min(seq[i].second - 3, n - 1));
seq[i].second -= min(seq[i].second, n + 2);
}
if (seq[i].second)
i--;
}
else
{
while (seq[i].second)
{
code.push_back(e);
code.push_back(e);
code.push_back(min(seq[i].second - 1, n - 1));
seq[i].second -= min(seq[i].second, n);
}
}
}
}
assert(code.size() == cost + q.top().first);
for (unsigned const &x : code)
cout << x << ' ';
cout << '\n';
}
Compilation message
rle.cpp: In function 'int main()':
rle.cpp:116:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<unsigned int, long unsigned int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (int64_t i = 0; i < seq.size(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Runtime error |
9 ms |
2636 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
58 ms |
11132 KB |
Execution killed with signal 6 |
| 8 |
Runtime error |
83 ms |
13296 KB |
Execution killed with signal 6 |
| 9 |
Runtime error |
183 ms |
65156 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
56 ms |
10568 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
47 ms |
9948 KB |
Execution killed with signal 6 |
| 12 |
Runtime error |
142 ms |
39236 KB |
Execution killed with signal 6 |
| 13 |
Runtime error |
117 ms |
22456 KB |
Execution killed with signal 6 |
| 14 |
Runtime error |
85 ms |
22388 KB |
Execution killed with signal 6 |
| 15 |
Runtime error |
36 ms |
14888 KB |
Execution killed with signal 6 |
| 16 |
Runtime error |
123 ms |
18904 KB |
Execution killed with signal 6 |
| 17 |
Runtime error |
160 ms |
35596 KB |
Execution killed with signal 6 |
| 18 |
Runtime error |
187 ms |
54728 KB |
Execution killed with signal 6 |
| 19 |
Correct |
644 ms |
92228 KB |
Output is correct |
| 20 |
Correct |
994 ms |
135544 KB |
Output is correct |
