Submission #137602

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137602	2019-07-28T07:20:47 Z	윤교준(#3280)	RLE (BOI06_rle)	C++14	0 / 100	535 ms	43988 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;

const int MAXN = 100055;
const int MAXK = 2000055;

struct SOL {
	SOL() : 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], B[MAXK];

int N, K;

void runNoChange() {
	SOL sol;
	for(int i = 0; i < K; i++) {
		if(!A[i]) {
			int k = B[i];
			for(int t; k;) {
				t = min(N, k);
				sol.push(0);
				sol.push(0);
				sol.push(t-1);
				k -= t;
			}
		} else {
			int c = A[i], k = B[i];
			for(int t; k;) {
				if(k < 3) {
					sol.push(c);
					k--;
					continue;
				}
				t = min(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], k = B[i];
		for(int t; k;) {
			if(k < 3) {
				sol.push(c);
				k--;
				continue;
			}
			t = min(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

#	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	504 KB	the output code does not encode the input sequence
5	Incorrect	2 ms	376 KB	the output code does not encode the input sequence
6	Incorrect	21 ms	1684 KB	the output code does not encode the input sequence
7	Incorrect	152 ms	10388 KB	the output code does not encode the input sequence
8	Incorrect	214 ms	16800 KB	the output code does not encode the input sequence
9	Incorrect	337 ms	24664 KB	the output code does not encode the input sequence
10	Incorrect	156 ms	10640 KB	the output code does not encode the input sequence
11	Incorrect	127 ms	9544 KB	the output code does not encode the input sequence
12	Incorrect	233 ms	19864 KB	the output code does not encode the input sequence
13	Incorrect	322 ms	22292 KB	the output code does not encode the input sequence
14	Incorrect	97 ms	7364 KB	the output code does not encode the input sequence
15	Incorrect	51 ms	3856 KB	the output code does not encode the input sequence
16	Incorrect	384 ms	33192 KB	the output code does not encode the input sequence
17	Incorrect	369 ms	25156 KB	the output code does not encode the input sequence
18	Incorrect	535 ms	30256 KB	Output is corrupted
19	Incorrect	454 ms	43988 KB	code is not the shortest
20	Incorrect	475 ms	43864 KB	code is not the shortest