# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
137639 |
2019-07-28T07:56:43 Z |
윤교준(#3280) |
RLE (BOI06_rle) |
C++14 |
|
703 ms |
524292 KB |
#include <bits/stdc++.h>
#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<int, ll> pil;
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;
int **dp, **dpi;
int A[MAXK]; ll B[MAXK];
int C[MAXK], D[MAXK], Del[MAXK];
int N, K;
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 process() {
dp = new int*[K+1];
dpi = new int*[K+1];
for(int i = 0; i <= K; i++) {
dp[i] = new int[N];
fill(dp[i], dp[i]+N, INF);
dpi[i] = new int[N];
}
dp[0][0] = 0;
for(int i = 0; i < K; i++) {
int totmni = int(min_element(dp[i], dp[i]+N) - dp[i]);
int totmn = dp[i][totmni];
for(int j = 0; j < N; j++) {
if(totmn < dp[i][j]-3) {
dp[i+1][j] = totmn;
dpi[i+1][j] = totmni;
} else {
dp[i+1][j] = dp[i][j]-3;
dpi[i+1][j] = j;
}
if(j == A[i]) dp[i+1][j] += Del[i];
}
}
vector<int> V;
int j = int(min_element(dp[K], dp[K]+N) - dp[K]);
for(int i = K; i--;) {
V.eb(j);
j = dpi[i+1][j];
}
revv(V);
makeSeq(V);
}
void precal() {
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];
}
}
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() {
ios_base::sync_with_stdio(0); cin.tie(0);
int L; cin >> N >> L;
vector<pii> T;
vector<int> V(L);
for(int i = 0; i < L; i++) cin >> 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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
504 KB |
Output is correct |
5 |
Correct |
3 ms |
1016 KB |
Output is correct |
6 |
Correct |
25 ms |
3608 KB |
Output is correct |
7 |
Correct |
177 ms |
21344 KB |
Output is correct |
8 |
Correct |
250 ms |
31520 KB |
Output is correct |
9 |
Correct |
468 ms |
94268 KB |
Output is correct |
10 |
Correct |
168 ms |
17752 KB |
Output is correct |
11 |
Correct |
270 ms |
91596 KB |
Output is correct |
12 |
Correct |
563 ms |
209664 KB |
Output is correct |
13 |
Correct |
496 ms |
120212 KB |
Output is correct |
14 |
Runtime error |
479 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
15 |
Runtime error |
465 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
16 |
Correct |
432 ms |
53548 KB |
Output is correct |
17 |
Runtime error |
644 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
18 |
Runtime error |
643 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
19 |
Runtime error |
703 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
20 |
Runtime error |
695 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |