| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 698100 |
2023-02-12T10:31:14 Z |
finn__ |
RLE (BOI06_rle) |
C++17 |
|
1020 ms |
146480 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)
{
if (!seq.empty() && seq.back().first == x)
seq.back().second += z + 1;
else
seq.emplace_back(x, z + 1);
}
else
{
if (z)
{
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;
vector<pair<uint64_t, unsigned>> removed;
while (1)
{
if (dp[q.top().second] == q.top().first && q.top().second == l)
{
removed.push_back(q.top());
q.pop();
}
else if (dp[q.top().second] != q.top().first)
q.pop();
else
break;
}
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] = dp[l] + additional_cost[i];
for (auto const &p : removed)
q.push(p);
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);
}
}
}
}
for (unsigned const &x : code)
cout << x << ' ';
cout << '\n';
}
Compilation message
rle.cpp: In function 'int main()':
rle.cpp:128: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]
128 | for (int64_t i = 0; i < seq.size(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
the output code does not encode the input sequence |
| 2 |
Incorrect |
1 ms |
212 KB |
Output is corrupted |
| 3 |
Incorrect |
1 ms |
320 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
1 ms |
340 KB |
the output code does not encode the input sequence |
| 5 |
Correct |
1 ms |
328 KB |
Output is correct |
| 6 |
Incorrect |
16 ms |
1692 KB |
the output code does not encode the input sequence |
| 7 |
Incorrect |
120 ms |
9800 KB |
the output code does not encode the input sequence |
| 8 |
Incorrect |
137 ms |
12960 KB |
the output code does not encode the input sequence |
| 9 |
Incorrect |
271 ms |
38996 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
114 ms |
9076 KB |
the output code does not encode the input sequence |
| 11 |
Incorrect |
102 ms |
9296 KB |
the output code does not encode the input sequence |
| 12 |
Incorrect |
204 ms |
29996 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
243 ms |
22800 KB |
the output code does not encode the input sequence |
| 14 |
Incorrect |
94 ms |
14628 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
47 ms |
9348 KB |
the output code does not encode the input sequence |
| 16 |
Incorrect |
256 ms |
24360 KB |
the output code does not encode the input sequence |
| 17 |
Incorrect |
333 ms |
33028 KB |
the output code does not encode the input sequence |
| 18 |
Incorrect |
318 ms |
43056 KB |
the output code does not encode the input sequence |
| 19 |
Correct |
702 ms |
103368 KB |
Output is correct |
| 20 |
Correct |
1020 ms |
146480 KB |
Output is correct |
