# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
137934 |
2019-07-28T14:32:56 Z |
sebinkim |
RLE (BOI06_rle) |
C++14 |
|
748 ms |
112860 KB |
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
vector <pll> X;
vector <ll> V[2020202], A;
ll D[101010], I[101010], P[2020202];
ll n, m, s, mv;
ll cost(ll x, ll t)
{
if(t) return ((x - 1) / n + 1) * 3;
else return x / (n + 2) * 3 + min(x % (n + 2), 3ll);
}
void insert(ll p)
{
ll d = D[p] % 4;
I[p] = V[d].size();
V[d].pb(p);
}
void erase(ll p)
{
ll d = D[p] % 4, q = V[d].back();
swap(V[d][I[p]], V[d].back());
swap(I[p], I[q]);
V[d].pop_back();
}
void change(ll &e, ll x)
{
printf("%lld %lld 0 ", e, x);
e = x;
}
ll make(ll x, ll y, ll e)
{
ll t;
if(x == e){
for(; y; ){
t = (y >= n? n - 1 : y - 1);
printf("%lld %lld %lld ", e, e, t);
y -= t + 1;
}
}
else{
for(; y; ){
t = (y >= n + 2? n - 1 : y - 3);
if(t == -2) printf("%lld ", x);
else if(t == -1) printf("%lld %lld ", x, x);
else if(t == 0) printf("%lld %lld %lld ", x, x, x);
else printf("%lld %lld %lld ", e, x, t);
y -= t + 3;
}
}
}
int main()
{
ll i, e, a, b, c, x, y, v;
scanf("%lld%lld", &n, &m);
for(i=0, e=0; i<m; i++){
scanf("%lld", &a);
if(a == e){
scanf("%lld%lld", &b, &c);
if(b == e) x = e, y = c + 1;
else if(c == 0) e = b, y = 0;
else x = b, y = c + 3;
i += 2;
}
else x = a, y = 1;
if(!y) continue;
else if(!X.empty() && X.back().first == x) X.back().second += y;
else X.emplace_back(x, y);
}
m = X.size();
mv = 0;
for(i=0; i<n; i++){
insert(i);
}
for(i=m-1; i>=0; i--){
tie(x, y) = X[i];
v = cost(y, 0); c = cost(y, 1) - v; s += v;
if(c == 0) continue;
erase(x);
for(; V[mv % 4].empty(); mv++);
if(D[x] + c > mv + 3){
P[i] = V[mv % 4].back() + 1;
D[x] = mv + 3;
}
else D[x] += c;
insert(x);
}
printf("%lld\n", s + D[0]);
for(i=0, e=0; i<m; i++){
tie(x, y) = X[i];
if(x == e && P[i]) change(e, P[i] - 1);
make(x, y, e);
}
printf("\n");
return 0;
}
Compilation message
rle.cpp: In function 'll make(ll, ll, ll)':
rle.cpp:63:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
rle.cpp: In function 'int main()':
rle.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~
rle.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &a);
~~~~~^~~~~~~~~~~~
rle.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
47736 KB |
Output is correct |
2 |
Incorrect |
46 ms |
47736 KB |
code is not the shortest |
3 |
Correct |
52 ms |
47832 KB |
Output is correct |
4 |
Incorrect |
48 ms |
47864 KB |
Unexpected end of file - int32 expected |
5 |
Correct |
58 ms |
47736 KB |
Output is correct |
6 |
Incorrect |
65 ms |
48500 KB |
Unexpected end of file - int32 expected |
7 |
Incorrect |
183 ms |
51180 KB |
Unexpected end of file - int32 expected |
8 |
Incorrect |
231 ms |
52420 KB |
code is not the shortest |
9 |
Incorrect |
409 ms |
66676 KB |
Unexpected end of file - int32 expected |
10 |
Incorrect |
187 ms |
50544 KB |
code is not the shortest |
11 |
Correct |
160 ms |
51692 KB |
Output is correct |
12 |
Incorrect |
287 ms |
62392 KB |
code is not the shortest |
13 |
Incorrect |
343 ms |
56548 KB |
code is not the shortest |
14 |
Correct |
153 ms |
54748 KB |
Output is correct |
15 |
Correct |
101 ms |
51520 KB |
Output is correct |
16 |
Correct |
355 ms |
58488 KB |
Output is correct |
17 |
Correct |
396 ms |
61972 KB |
Output is correct |
18 |
Correct |
419 ms |
66512 KB |
Output is correct |
19 |
Correct |
723 ms |
98896 KB |
Output is correct |
20 |
Correct |
748 ms |
112860 KB |
Output is correct |