Submission #137610

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137610	2019-07-28T07:31:06 Z	윤교준(#3280)	RLE (BOI06_rle)	C++14	5 / 100	465 ms	51800 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();

	if(10000000 < N*K) return -1;

	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	504 KB	code is not the shortest
5	Incorrect	2 ms	376 KB	code is not the shortest
6	Incorrect	21 ms	1684 KB	code is not the shortest
7	Incorrect	154 ms	10612 KB	code is not the shortest
8	Incorrect	215 ms	16968 KB	code is not the shortest
9	Incorrect	337 ms	26404 KB	code is not the shortest
10	Incorrect	159 ms	10636 KB	code is not the shortest
11	Incorrect	127 ms	9804 KB	code is not the shortest
12	Runtime error	138 ms	18736 KB	Execution failed because the return code was nonzero
13	Runtime error	187 ms	17016 KB	Execution failed because the return code was nonzero
14	Runtime error	61 ms	7268 KB	Execution failed because the return code was nonzero
15	Runtime error	33 ms	3948 KB	Execution failed because the return code was nonzero
16	Correct	382 ms	33276 KB	Output is correct
17	Runtime error	212 ms	18848 KB	Execution failed because the return code was nonzero
18	Incorrect	385 ms	27212 KB	code is not the shortest
19	Incorrect	460 ms	51740 KB	code is not the shortest
20	Incorrect	465 ms	51800 KB	code is not the shortest