Submission #137609

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137609	2019-07-28T07:28:45 Z	윤교준(#3280)	RLE (BOI06_rle)	C++14	5 / 100	497 ms	51752 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 < 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();
	Ans.n = INF;

	runNoChange();
	runNoAlphabet();

	Ans.prt();
	return 0;
}

Subtask #1

5.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	code is not the shortest
3	Incorrect	2 ms	376 KB	code is not the shortest
4	Incorrect	3 ms	376 KB	code is not the shortest
5	Incorrect	2 ms	376 KB	code is not the shortest
6	Incorrect	21 ms	1688 KB	code is not the shortest
7	Incorrect	163 ms	10620 KB	code is not the shortest
8	Incorrect	221 ms	16928 KB	code is not the shortest
9	Incorrect	335 ms	26308 KB	code is not the shortest
10	Incorrect	160 ms	10608 KB	code is not the shortest
11	Incorrect	126 ms	9824 KB	code is not the shortest
12	Incorrect	223 ms	21916 KB	code is not the shortest
13	Incorrect	325 ms	22684 KB	code is not the shortest
14	Incorrect	96 ms	8252 KB	code is not the shortest
15	Incorrect	50 ms	4500 KB	code is not the shortest
16	Correct	381 ms	33316 KB	Output is correct
17	Incorrect	364 ms	26552 KB	code is not the shortest
18	Incorrect	366 ms	27440 KB	code is not the shortest
19	Incorrect	497 ms	51752 KB	code is not the shortest
20	Incorrect	462 ms	51748 KB	code is not the shortest