| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 137778 |
2019-07-28T09:36:38 Z |
윤교준(#3280) |
RLE (BOI06_rle) |
C++14 |
|
2500 ms |
134112 KB |
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
static unsigned char str[22000022], *p=str;
const int MAXN = 100055;
const int MAXK = 2000055;
struct SOL {
SOL() : V(), n(0) {}
vector<int> V;
int n;
void push(int x) { V.eb(x); n++; }
void prt() const {
cout << n << '\n';
for(int v : V) cout << v << ' ';
cout << '\n';
}
bool operator < (const SOL &t) const {
return n < t.n;
}
} Ans;
struct SEG {
int dp[MAXN*3], dmn[MAXN*3];
pii di[MAXN*3];
int dmni[MAXN*3];
void init(int i, int s, int e) {
dp[i] = dmn[i] = INF;
di[i] = {s, -1};
dmni[i] = -1;
if(s == e) return;
int m = (s+e) >> 1;
init(i<<1, s, m);
init(i<<1|1, m+1, e);
}
void prop(int i, int s, int e) {
if(INF <= dmn[i]) return;
if(dmn[i] < dp[i]) {
dp[i] = dmn[i];
di[i] = {s, dmni[i]};
}
if(s != e) {
if(dmn[i] < dmn[i<<1]) {
dmn[i<<1] = dmn[i];
dmni[i<<1] = dmni[i];
}
if(dmn[i] < dmn[i<<1|1]) {
dmn[i<<1|1] = dmn[i];
dmni[i<<1|1] = dmni[i];
}
}
dmn[i] = INF;
}
void cal(int i) {
int j = dp[i<<1] < dp[i<<1|1] ? (i<<1) : (i<<1|1);
dp[i] = dp[j];
di[i] = di[j];
}
void upd(int i, int s, int e, int x, ll r) {
prop(i, s, e); if(x < s || e < x) return;
if(s == e) {
dp[i] += r;
return;
}
int m = (s+e) >> 1;
upd(i<<1, s, m, x, r);
upd(i<<1|1, m+1, e, x, r);
cal(i);
}
void upd(int i, int s, int e, int p, int q, int x, ll r) {
prop(i, s, e); if(q < p || e < p || q < s) return;
if(p <= s && e <= q) {
dmn[i] = r;
dmni[i] = x;
prop(i, s, e);
return;
}
int m = (s+e) >> 1;
upd(i<<1, s, m, p, q, r);
upd(i<<1|1, m+1, e, p, q, r);
cal(i);
}
void upd(int i, int s, int e, int x, int y, ll r) {
prop(i, s, e); if(x < s || e < x) return;
if(s == e) {
dp[i] = r;
di[i] = {x, y};
return;
}
int m = (s+e) >> 1;
upd(i<<1, s, m, x, y, r);
upd(i<<1|1, m+1, e, x, y, r);
cal(i);
}
pair<int, pii> get(int i, int s, int e, int p, int q) {
prop(i, s, e); if(q < p || e < p || q < s) return {INF, {-1, -1}};
if(p <= s && e <= q) return {dp[i], di[i]};
int m = (s+e) >> 1;
auto ret = min(get(i<<1, s, m, p, q), get(i<<1|1, m+1, e, p, q));
cal(i);
return ret;
}
} seg;
vector<pii> SDel[MAXN];
vector<int> AI[MAXN];
int dp[MAXK], bfi[MAXK], bfc[MAXK];
int A[MAXK]; ll B[MAXK];
int C[MAXK], D[MAXK], Del[MAXK];
int N, K;
void makeSeq(const vector<int>&);
int sigDel(int c, int x) { return prev(lower_bound(allv(SDel[c]), pii(x, -INF))) -> second; }
void process() {
seg.init(1, 0, N-1);
for(int i = 0;; i++) {
vector<int> AV;
if(i < K) {
AV.eb(0);
if(A[i]) AV.eb(A[i]);
}
else for(int j = 0; j < N; j++) AV.eb(j);
dp[i] = INF;
auto upd = [&](int c, int j, int t) {
if(dp[i] <= t) return;
dp[i] = t;
bfi[i] = j;
bfc[i] = c;
};
for(int a : AV) upd(a, 0, sigDel(a, i) - 3*(a ? (i-1) : i));
pair<int, pii> ret = seg.get(1, 0, N-1, 0, N-1);
if(ret.first < INF) {
ret.first -= 3*i;
upd(ret.second.first, ret.second.second, ret.first);
}
if(i == K) break;
seg.upd(1, 0, N-1, 0, N-1, i, dp[i] + 3*i + 3);
seg.upd(1, 0, N-1, A[i], Del[i]);
}
vector<int> V;
for(int i = K, ni, nc; i;) {
ni = bfi[i]; nc = bfc[i];
for(; ni < i; i--) V.eb(nc);
}
revv(V);
makeSeq(V);
}
void makeSeq(const vector<int> &XV) {
SOL sol;
for(int i = 0, x = 0, y; i < K; i++) {
y = XV[i];
if(x != y) {
sol.push(x);
sol.push(y);
sol.push(0);
x = y;
}
if(x == A[i]) {
ll k = B[i];
for(ll t; k;) {
t = min(ll(N), k);
sol.push(x);
sol.push(x);
sol.push(t-1);
k -= t;
}
} else {
int c = A[i]; ll k = B[i];
for(ll t; k;) {
if(k < 4) {
sol.push(c);
k--;
continue;
}
t = min(ll(N+2), k);
sol.push(x);
sol.push(c);
sol.push(t-3);
k -= t;
}
}
}
if(sol < Ans) swap(Ans, sol);
}
void precal() {
for(int i = 0; i < N; i++) SDel[i].eb(-1, 0);
for(int i = 0; i < K; i++) {
ll k = B[i], ret = 0;
for(ll t; k;) {
if(k < 4) {
ret += k;
break;
}
t = min(ll(N+2), k);
ret += 3;
k -= t;
}
C[i] = ret;
k = B[i]; ret = 0;
for(ll t; k;) {
t = min(ll(N), k);
ret += 3;
k -= t;
}
D[i] = ret;
Del[i] = D[i] - C[i];
AI[A[i]].eb(i);
SDel[A[i]].eb(i, SDel[A[i]].back().second + Del[i]);
}
}
void runNoChange() {
SOL sol;
for(int i = 0; i < K; i++) {
if(!A[i]) {
ll k = B[i];
for(ll t; k;) {
t = min(ll(N), k);
sol.push(0);
sol.push(0);
sol.push(t-1);
k -= t;
}
} else {
int c = A[i]; ll k = B[i];
for(ll t; k;) {
if(k < 4) {
sol.push(c);
k--;
continue;
}
t = min(ll(N+2), k);
sol.push(0);
sol.push(c);
sol.push(t-3);
k -= t;
}
}
}
if(sol < Ans) swap(Ans, sol);
}
void runNoAlphabet() {
bitset<MAXN> chk;
for(int i = 0; i < K; i++) chk[A[i]] = true;
int x = 1; for(; x < N && chk[x]; x++);
if(x == N) return;
SOL sol;
sol.push(0); sol.push(x); sol.push(0);
for(int i = 0; i < K; i++) {
int c = A[i]; ll k = B[i];
for(int t; k;) {
if(k < 4) {
sol.push(c);
k--;
continue;
}
t = min(ll(N+2), k);
sol.push(x);
sol.push(c);
sol.push(t-3);
k -= t;
}
}
if(sol < Ans) swap(Ans, sol);
}
void input() {
fread(str, 1, 22000022, stdin);
int L; rf(N) rf(L)
vector<pii> T;
vector<int> V(L);
for(int i = 0; i < L; i++) { rf(V[i]) }
for(int i = 0, x = 0; i < L;) {
if(V[i] != x) {
T.eb(V[i], 1);
i++;
} else if(x == V[i+1]) {
T.eb(x, V[i+2]+1);
i += 3;
} else if(!V[i+2]) {
x = V[i+1];
i += 3;
} else {
T.eb(V[i+1], V[i+2]+3);
i += 3;
}
}
for(auto &v : T) {
int a, b; tie(a, b) = v;
if(K && A[K-1] == a) B[K-1] += b;
else {
A[K] = a; B[K] = b;
K++;
}
}
}
int main() {
input();
precal();
Ans.n = INF;
//runNoChange();
//runNoAlphabet();
process();
Ans.prt();
return 0;
}
Compilation message
rle.cpp: In function 'void input()':
rle.cpp:296:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(str, 1, 22000022, stdin);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
10 ms |
7416 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7544 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7548 KB |
Output is correct |
| 5 |
Correct |
9 ms |
7544 KB |
Output is correct |
| 6 |
Correct |
26 ms |
9620 KB |
Output is correct |
| 7 |
Correct |
138 ms |
21900 KB |
Output is correct |
| 8 |
Correct |
182 ms |
29212 KB |
Output is correct |
| 9 |
Correct |
432 ms |
63756 KB |
Output is correct |
| 10 |
Correct |
132 ms |
20712 KB |
Output is correct |
| 11 |
Correct |
121 ms |
21836 KB |
Output is correct |
| 12 |
Correct |
383 ms |
52380 KB |
Output is correct |
| 13 |
Correct |
323 ms |
40084 KB |
Output is correct |
| 14 |
Correct |
205 ms |
26460 KB |
Output is correct |
| 15 |
Correct |
119 ms |
17800 KB |
Output is correct |
| 16 |
Correct |
263 ms |
39636 KB |
Output is correct |
| 17 |
Correct |
508 ms |
52968 KB |
Output is correct |
| 18 |
Correct |
634 ms |
61528 KB |
Output is correct |
| 19 |
Execution timed out |
2556 ms |
134112 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2568 ms |
132236 KB |
Time limit exceeded |
