| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 137711 |
2019-07-28T08:53:29 Z |
김현수(#3360) |
RLE (BOI06_rle) |
C++14 |
|
1416 ms |
45952 KB |
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
const int N = 2000005, L = 131072, inf = 1e9;
int m, n, rn, a[N], c[N], wh[L], sw[N], crm;
vector<int> ans;
int cost1 (int L) {return (L+m-1)/m*3;}
void make1 (int L) {
while(L) {
int C = min(m-1, L-1);
ans.push_back(C);
ans.push_back(crm);
ans.push_back(crm);
L -= C+1;
}
}
int cost2 (int L) {
int R = L%(m+2);
if(R == 0 || R > 2) return (L+m+1)/(m+2)*3;
else return L/(m+2)*3+R;
}
void make2 (int L, int I) {
while(L >= 3) {
int C = min(m-1, L-3);
ans.push_back(C);
ans.push_back(I);
ans.push_back(crm);
L -= C + 3;
}
while(L) {
ans.push_back(I);
L--;
}
}
void swit (int I) {
ans.push_back(0);
ans.push_back(I);
ans.push_back(crm);
}
struct segtree {
pii v[2*L];
void init () {
for(int i=1;i<m;i++) {
v[i+L] = {3, i};
}
for(int i=L;--i;) {
v[i] = min(v[2*i], v[2*i+1]);
}
}
void upd (int P, int V) {
P += L; v[P].X += V; P /= 2;
while(P) {
v[P] = min(v[2*P], v[2*P+1]);
P /= 2;
}
}
pii get (int S, int E) {
S += L; E += L;
pii R = {inf, inf};
while(S <= E) {
if(S%2 == 1) R = min(R, v[S++]);
if(E%2 == 0) R = min(R, v[E--]);
S /= 2; E /= 2;
}
return R;
}
} seg;
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++) {
int T;
scanf("%d",&T);
if(!rn || a[T] != a[rn]) rn++;
a[rn] = T;
c[rn]++;
}
for(int i=1;i<=m;i++) {
wh[i] = 3;
}
seg.init();
for(int i=1;i<=rn;i++) {
int X = cost1(c[i]) - cost2(c[i]);
auto V1 = min(seg.get(0, a[i]-1), seg.get(a[i]+1, m-1)), V2 = seg.get(a[i], a[i]);
if(X > V1.X - V2.X + 3) {
seg.upd(a[i], V1.X - V2.X + 3);
sw[i] = V1.Y;
}
else seg.upd(a[i], X);
}
crm = seg.get(0, m-1).Y;
for(int i=rn;i>=1;i--) {
if(crm == a[i] && sw[i]) swit(sw[i]);
if(crm == a[i]) make1(c[i]);
else make2(c[i], a[i]);
}
if(crm != 0) swit(0);
printf("%d\n", ans.size());
for(int i=ans.size();i--;) {
printf("%d ", ans[i]);
}
}
Compilation message
rle.cpp: In function 'int main()':
rle.cpp:109:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%d\n", ans.size());
~~~~~~~~~~^
rle.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&m,&n);
~~~~~^~~~~~~~~~~~~~
rle.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&T);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1400 KB |
the output code does not encode the input sequence |
| 2 |
Incorrect |
4 ms |
1400 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
4 ms |
1400 KB |
the output code does not encode the input sequence |
| 4 |
Incorrect |
5 ms |
1528 KB |
the output code does not encode the input sequence |
| 5 |
Incorrect |
4 ms |
1400 KB |
the output code does not encode the input sequence |
| 6 |
Incorrect |
38 ms |
3308 KB |
the output code does not encode the input sequence |
| 7 |
Incorrect |
305 ms |
18468 KB |
the output code does not encode the input sequence |
| 8 |
Incorrect |
391 ms |
22784 KB |
the output code does not encode the input sequence |
| 9 |
Incorrect |
526 ms |
25552 KB |
the output code does not encode the input sequence |
| 10 |
Incorrect |
316 ms |
19164 KB |
the output code does not encode the input sequence |
| 11 |
Incorrect |
245 ms |
13792 KB |
the output code does not encode the input sequence |
| 12 |
Incorrect |
447 ms |
22496 KB |
the output code does not encode the input sequence |
| 13 |
Incorrect |
596 ms |
35396 KB |
the output code does not encode the input sequence |
| 14 |
Incorrect |
217 ms |
10212 KB |
the output code does not encode the input sequence |
| 15 |
Incorrect |
113 ms |
6136 KB |
the output code does not encode the input sequence |
| 16 |
Incorrect |
660 ms |
40324 KB |
the output code does not encode the input sequence |
| 17 |
Incorrect |
765 ms |
40440 KB |
the output code does not encode the input sequence |
| 18 |
Incorrect |
853 ms |
41672 KB |
the output code does not encode the input sequence |
| 19 |
Incorrect |
1302 ms |
45948 KB |
the output code does not encode the input sequence |
| 20 |
Incorrect |
1416 ms |
45952 KB |
the output code does not encode the input sequence |
