| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 137608 |
2019-07-28T07:26:50 Z |
윤교준(#3280) |
RLE (BOI06_rle) |
C++14 |
|
477 ms |
51888 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 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 A[MAXK]; ll B[MAXK];
int N, K;
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 < 3) {
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 < 3) {
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();
Ans.n = INF;
runNoChange();
runNoAlphabet();
Ans.prt();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
code is not the shortest |
| 2 |
Incorrect |
2 ms |
376 KB |
the output code does not encode the input sequence |
| 3 |
Incorrect |
2 ms |
376 KB |
the output code does not encode the input sequence |
| 4 |
Incorrect |
3 ms |
376 KB |
the output code does not encode the input sequence |
| 5 |
Incorrect |
2 ms |
504 KB |
the output code does not encode the input sequence |
| 6 |
Incorrect |
21 ms |
1712 KB |
the output code does not encode the input sequence |
| 7 |
Incorrect |
162 ms |
10684 KB |
the output code does not encode the input sequence |
| 8 |
Incorrect |
213 ms |
17056 KB |
the output code does not encode the input sequence |
| 9 |
Incorrect |
336 ms |
26308 KB |
the output code does not encode the input sequence |
| 10 |
Incorrect |
159 ms |
10600 KB |
the output code does not encode the input sequence |
| 11 |
Incorrect |
124 ms |
9796 KB |
the output code does not encode the input sequence |
| 12 |
Incorrect |
225 ms |
21608 KB |
the output code does not encode the input sequence |
| 13 |
Incorrect |
326 ms |
22952 KB |
the output code does not encode the input sequence |
| 14 |
Incorrect |
99 ms |
8132 KB |
the output code does not encode the input sequence |
| 15 |
Incorrect |
50 ms |
4368 KB |
the output code does not encode the input sequence |
| 16 |
Incorrect |
384 ms |
33216 KB |
the output code does not encode the input sequence |
| 17 |
Incorrect |
365 ms |
25928 KB |
the output code does not encode the input sequence |
| 18 |
Incorrect |
373 ms |
26944 KB |
the output code does not encode the input sequence |
| 19 |
Incorrect |
472 ms |
51828 KB |
code is not the shortest |
| 20 |
Incorrect |
477 ms |
51888 KB |
code is not the shortest |
