답안 #137608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137608	2019-07-28T07:26:50 Z	윤교준(#3280)	RLE (BOI06_rle)	C++14	0 / 100	477 ms	51888 KB

rle

#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;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	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