| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 137716 |
2019-07-28T09:00:08 Z |
김세빈(#3278) |
RLE (BOI06_rle) |
C++14 |
|
760 ms |
96408 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[4], 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;
swap(V[d][I[p]], V[d].back());
swap(I[p], I[V[d][I[p]]]);
V[d].pop_back();
}
void change(ll &e, ll x)
{
A.pb(e); A.pb(x); A.pb(0);
e = x;
}
void make(ll x, ll y, ll e)
{
ll t;
if(x == e){
for(; y; ){
t = (y >= n? n - 1 : y - 1);
A.pb(e); A.pb(e); A.pb(t);
y -= t + 1;
}
}
else{
for(; y; ){
t = (y >= n + 2? n - 1 : y - 3);
if(t == -2) A.pb(x);
else if(t == -1) A.pb(x), A.pb(x);
else if(t == 0) A.pb(x), A.pb(x), A.pb(x);
else A.pb(e), A.pb(x), A.pb(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); 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);
}
if(A.size() != s + D[0]) return 1 / 0;
for(i=0; i<A.size(); i++){
printf("%lld%c", A[i], " \n"[i == A.size() - 1]);
}
return 0;
}
Compilation message
rle.cpp: In function 'int main()':
rle.cpp:115:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(A.size() != s + D[0]) return 1 / 0;
~~~~~~~~~^~~~~~~~~~~
rle.cpp:115:36: warning: division by zero [-Wdiv-by-zero]
if(A.size() != s + D[0]) return 1 / 0;
~~^~~
rle.cpp:117:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<A.size(); i++){
~^~~~~~~~~
rle.cpp:118:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
printf("%lld%c", A[i], " \n"[i == A.size() - 1]);
~~^~~~~~~~~~~~~~~
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 |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
code is not the shortest |
| 3 |
Correct |
2 ms |
380 KB |
Output is correct |
| 4 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 4 (could be triggered by violating memory limits) |
| 5 |
Incorrect |
2 ms |
376 KB |
code is not the shortest |
| 6 |
Runtime error |
18 ms |
3452 KB |
Execution killed with signal 4 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
105 ms |
16932 KB |
Execution killed with signal 4 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
142 ms |
21956 KB |
Execution killed with signal 4 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
312 ms |
58012 KB |
Execution killed with signal 4 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
107 ms |
17492 KB |
Execution killed with signal 4 (could be triggered by violating memory limits) |
| 11 |
Incorrect |
147 ms |
9952 KB |
code is not the shortest |
| 12 |
Runtime error |
216 ms |
41648 KB |
Execution killed with signal 4 (could be triggered by violating memory limits) |
| 13 |
Incorrect |
385 ms |
23928 KB |
code is not the shortest |
| 14 |
Correct |
128 ms |
11356 KB |
Output is correct |
| 15 |
Correct |
66 ms |
6244 KB |
Output is correct |
| 16 |
Correct |
419 ms |
26560 KB |
Output is correct |
| 17 |
Correct |
445 ms |
33984 KB |
Output is correct |
| 18 |
Correct |
468 ms |
42816 KB |
Output is correct |
| 19 |
Correct |
735 ms |
83268 KB |
Output is correct |
| 20 |
Correct |
760 ms |
96408 KB |
Output is correct |
