| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 137777 |
2019-07-28T09:36:19 Z |
김세빈(#3278) |
RLE (BOI06_rle) |
C++14 |
|
736 ms |
112680 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 0 ", e, x, 0);
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; erase(x);
if(c == 0) insert(x);
else{
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 'void change(ll&, ll)':
rle.cpp:38:27: warning: too many arguments for format [-Wformat-extra-args]
printf("%lld 0 ", e, x, 0);
^
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);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
45 ms |
47736 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
45 ms |
47736 KB |
code is not the shortest |
| 3 |
Incorrect |
46 ms |
47864 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
46 ms |
47864 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
46 ms |
47864 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
64 ms |
48500 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
186 ms |
51224 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
233 ms |
52476 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
407 ms |
66744 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
189 ms |
50448 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
174 ms |
51564 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
302 ms |
62504 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
343 ms |
56412 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
152 ms |
54492 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
100 ms |
51560 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
359 ms |
58464 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
405 ms |
61968 KB |
Unexpected end of file - int32 expected |
| 18 |
Incorrect |
418 ms |
67024 KB |
Unexpected end of file - int32 expected |
| 19 |
Incorrect |
718 ms |
98968 KB |
Unexpected end of file - int32 expected |
| 20 |
Incorrect |
736 ms |
112680 KB |
Unexpected end of file - int32 expected |
