| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 137786 |
2019-07-28T09:40:48 Z |
이온조(#3279) |
RLE (BOI06_rle) |
C++14 |
|
2500 ms |
139300 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pil = pair<int, long long>;
using tiii = tuple<int, int, int>;
#define X first
#define Y second
#define sz(V) ((int)V.size())
int N, M, K, A[2000009], mn[100009], mni[100009], fi[2000009], se[2000009], wh[4000009], ch[4000009];
int ofs, del[100009];
set<pii> col, st;
vector<pil> S;
void add(int a, int b) {
if(S.empty()) S.push_back({a, b});
else {
if(S.back().X == a) S[sz(S) - 1].Y += b;
else S.push_back({a, b});
}
}
inline int get(int x) { return ofs + del[x]; }
vector<int> get4(int i) {
int cnt = 4;
vector<int> ret;
for(auto& it: st) {
ret.push_back(it.Y);
if(--cnt == 0) break;
}
return ret;
}
pii getfi() { return (*col.begin()); }
pii getse() { return (*next(col.begin())); }
void upd(int i) {
int el, me;
int mod = S[i].Y % (N + 2);
el = (S[i].Y) / (N + 2) * 3 + min(mod, 3);
me = ((S[i].Y - 1) / N + 1) * 3;
ofs += el;
st.erase({del[S[i].X], S[i].X});
del[S[i].X] += me - el;
st.insert({del[S[i].X], S[i].X});
}
int f(int pos) { return pos <= K ? pos : pos - K; }
void go(int now) {
if(now == 0) return;
go(wh[now]);
if(wh[now] != 0 || ch[now] != 0) printf("%d %d %d ", ch[wh[now]], ch[now], 0);
for(int i=f(wh[now]) + 1; i<=f(now); i++) {
while(S[i].Y > 0) {
if(S[i].X == ch[now]) {
printf("%d %d %d ", ch[now], ch[now], min(1LL*N, S[i].Y) - 1);
S[i].Y -= min(1LL*N, S[i].Y);
}
else {
printf("%d %d %d ", ch[now], S[i].X, min(1LL*N+2, S[i].Y) - 3);
S[i].Y -= min(1LL*N+2, S[i].Y);
}
}
}
}
int main() {
scanf("%d%d",&N,&M);
for(int i=1; i<=M; i++) scanf("%d", &A[i]);
for(int i=1, r=0; i<=M; i++) {
if(A[i] == r) {
if(A[i+1] == r) add(r, A[i+2] + 1);
else if(A[i+2] == 0) r = A[i+1];
else add(A[i+1], A[i+2] + 3);
i += 2;
}
else add(A[i], 1);
}
K = sz(S);
S.insert(S.begin(), {0, 0});
for(int i=0; i<N; i++) {
st.insert({0, i});
if(i <= 1) mn[i] = 0, mni[i] = 0;
else mn[i] = 1e9, mni[i] = -1;
col.insert({mn[i], i});
}
fi[0] = 0; se[0] = 0;
for(int i=1; i<=K; i++) {
upd(i);
vector<int> T = get4(i); // 가장 작은 rm을 4개 꺼내온다.
vector<tiii> R;
for(auto& it: T) {
if(it == getfi().Y) {
int a, b; tie(a, b) = getse();
R.push_back((tiii){b + get(it) + 3 + (i == 1 ? -3 : 0), it, mni[a]});
}
else {
int a, b; tie(a, b) = getfi();
R.push_back((tiii){b + get(it) + 3, it, mni[a]});
}
}
sort(R.begin(), R.end());
int fa, fb, fc, fv; tie(fa, fb, fc) = R[0]; fv = fa - get(fb);
int sa, sb, sc, sv; tie(sa, sb, sc) = R[1]; sv = sa - get(sb);
printf("fa: %d, fb: %d, fc: %d\n", fa, fb, fc);
printf("sa: %d, sb: %d, sc: %d\n", sa, sb, sc);
fi[i] = fa; wh[i] = fc; ch[i] = sb;
if(mn[fb] > fv) {
col.erase({mn[fb], fb});
mn[fb] = fv, mni[fb] = i;
col.insert({mn[fb], fb});
}
se[i] = sa; wh[i + K] = sc; ch[i + K] = fb;
if(mn[sb] > sv) {
col.erase({mn[sb], sb});
mn[sb] = sv, mni[sb] = i + K;
col.insert({mn[sb], sb});
}
printf("first: %d, second: %d\n", fi[i], se[i]);
}
printf("%d\n", fi[K]);
go(K);
return 0;
}
Compilation message
rle.cpp: In function 'void go(int)':
rle.cpp:58:65: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
printf("%d %d %d ", ch[now], ch[now], min(1LL*N, S[i].Y) - 1);
~~~~~~~~~~~~~~~~~~~~~~^
rle.cpp:62:66: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
printf("%d %d %d ", ch[now], S[i].X, min(1LL*N+2, S[i].Y) - 3);
~~~~~~~~~~~~~~~~~~~~~~~~^
rle.cpp: In function 'int main()':
rle.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&N,&M);
~~~~~^~~~~~~~~~~~~~
rle.cpp:71:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=M; i++) scanf("%d", &A[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Expected integer, but "fa:" found |
| 2 |
Incorrect |
2 ms |
376 KB |
Expected integer, but "fa:" found |
| 3 |
Incorrect |
2 ms |
376 KB |
Expected integer, but "fa:" found |
| 4 |
Incorrect |
3 ms |
376 KB |
Expected integer, but "fa:" found |
| 5 |
Incorrect |
4 ms |
504 KB |
Expected integer, but "fa:" found |
| 6 |
Incorrect |
40 ms |
3060 KB |
Expected integer, but "fa:" found |
| 7 |
Incorrect |
208 ms |
11776 KB |
Expected integer, but "fa:" found |
| 8 |
Incorrect |
256 ms |
13656 KB |
Expected integer, but "fa:" found |
| 9 |
Incorrect |
1138 ms |
92556 KB |
Expected integer, but "fa:" found |
| 10 |
Incorrect |
189 ms |
9636 KB |
Expected integer, but "fa:" found |
| 11 |
Incorrect |
193 ms |
11500 KB |
Expected integer, but "fa:" found |
| 12 |
Incorrect |
871 ms |
67752 KB |
Expected integer, but "fa:" found |
| 13 |
Incorrect |
456 ms |
25572 KB |
Expected integer, but "fa:" found |
| 14 |
Incorrect |
426 ms |
29760 KB |
Expected integer, but "fa:" found |
| 15 |
Incorrect |
223 ms |
15204 KB |
Expected integer, but "fa:" found |
| 16 |
Incorrect |
342 ms |
17348 KB |
Expected integer, but "fa:" found |
| 17 |
Incorrect |
723 ms |
43844 KB |
Expected integer, but "fa:" found |
| 18 |
Incorrect |
1027 ms |
55504 KB |
Expected integer, but "fa:" found |
| 19 |
Execution timed out |
2606 ms |
139300 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2542 ms |
136964 KB |
Time limit exceeded |
