Submission #137605

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137605	2019-07-28T07:23:33 Z	임유진(#3281)	RLE (BOI06_rle)	C++14	65 / 100	1601 ms	33672 KB

rle

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define fi first
#define se second

const int MAXN = 100005;
const int MAXM = 2000005;

int inp[MAXM];
int num[MAXM], cnt[MAXM], nn;
int dp[MAXN];
int w[MAXN];
vector<int> ans;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M;

	cin >> N >> M;
	for(int i = 0; i < M; i++) cin >> inp[i];

	int e = 0;
	for(int i = 0; i < M;) {
		if(inp[i] != e) {
			num[nn] = inp[i];
			cnt[nn++] = 1;
			i++;
		}
		else if(inp[i + 1] == e) {
			num[nn] = e;
			cnt[nn++] = inp[i + 2] + 1;
			i += 3;
		}
		else if(inp[i + 2] == 0) {
			e = inp[i + 1];
			i += 3;
		}
		else {
			num[nn] = inp[i + 1];
			cnt[nn++] = inp[i + 2] + 3;
			i += 3;
		}
	}

	int t = 0;
	for(int i = 0; i < nn; i++) {
		if(i == 0 || num[i - 1] != num[i]) {
			num[t] = num[i];
			cnt[t++] = cnt[i];
		}
		else cnt[t - 1] += cnt[i];
	}
	nn = t;

	set<pii> s;
	for(int i = 0; i < N; i++) s.insert(make_pair(0, i));
	for(int i = nn - 1; i >= 0; i--) {
		int p = ((cnt[i] - 1) / N + 1) * 3;
		int q = cnt[i] / (N + 2) * 3 + min(cnt[i] % (N + 2), 3);
		s.erase(make_pair(dp[num[i]], num[i]));
		if(dp[num[i]] + p - q < s.begin() -> fi + 3) {
			dp[num[i]] += p - q;
			w[i] = num[i];
		}
		else {
			dp[num[i]] = s.begin() -> fi + 3;
			w[i] = s.begin() -> se;
		}
		s.insert(make_pair(dp[num[i]], num[i]));
	}

	e = 0;
	for(int i = 0; i < nn; i++) {
		if(num[i] == e) {
			if(w[i] == e) {
				while(cnt[i] > 0) {
					ans.push_back(e);
					ans.push_back(e);
					ans.push_back(min(N, cnt[i]) - 1);
					cnt[i] -= min(N, cnt[i]);
				}
				continue;
			}
			ans.push_back(e);
			ans.push_back(w[i]);
			ans.push_back(0);
			e = w[i];
		}
		while(cnt[i] > N + 2) {
			ans.push_back(e);
			ans.push_back(num[i]);
			ans.push_back(N - 1);
			cnt[i] -= N + 2;
		}
		if(cnt[i] <= 3) 
			for(int j = 0; j < cnt[i]; j++) ans.push_back(num[i]);
		else {
			ans.push_back(e);
			ans.push_back(num[i]);
			ans.push_back(cnt[i] - 3);
		}
	}

	cout << ans.size() << "\n";
	for(auto a : ans) cout << a << " ";
	return 0;
}

Subtask #1

65.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 ms	504 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	23 ms	2008 KB	Output is correct
7	Correct	160 ms	12524 KB	Output is correct
8	Correct	212 ms	17244 KB	Output is correct
9	Incorrect	225 ms	19320 KB	the output code does not encode the input sequence
10	Correct	153 ms	12896 KB	Output is correct
11	Correct	138 ms	10164 KB	Output is correct
12	Incorrect	208 ms	12444 KB	the output code does not encode the input sequence
13	Correct	348 ms	27484 KB	Output is correct
14	Incorrect	152 ms	9572 KB	code is not the shortest
15	Correct	84 ms	5360 KB	Output is correct
16	Correct	340 ms	29684 KB	Output is correct
17	Incorrect	264 ms	17116 KB	the output code does not encode the input sequence
18	Incorrect	379 ms	21912 KB	the output code does not encode the input sequence
19	Incorrect	1505 ms	33672 KB	the output code does not encode the input sequence
20	Incorrect	1601 ms	30456 KB	the output code does not encode the input sequence