Submission #137613

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137613	2019-07-28T07:33:03 Z	임유진(#3281)	RLE (BOI06_rle)	C++14	95 / 100	2122 ms	58676 KB

rle

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

typedef long long lint;
typedef pair<lint, int> pli;

#define fi first
#define se second

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

int inp[MAXM];
int num[MAXM], cnt[MAXM], nn;
lint dp[MAXN];
int w[MAXM];
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<pli> s;
	for(int i = 0; i < N; i++) s.insert(make_pair(0ll, 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

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 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	504 KB	Output is correct
6	Correct	21 ms	2036 KB	Output is correct
7	Correct	157 ms	12384 KB	Output is correct
8	Correct	212 ms	17336 KB	Output is correct
9	Correct	363 ms	30680 KB	Output is correct
10	Correct	153 ms	12896 KB	Output is correct
11	Correct	136 ms	10216 KB	Output is correct
12	Correct	313 ms	21980 KB	Output is correct
13	Correct	341 ms	27528 KB	Output is correct
14	Correct	152 ms	9596 KB	Output is correct
15	Correct	85 ms	5484 KB	Output is correct
16	Correct	340 ms	29888 KB	Output is correct
17	Correct	447 ms	33748 KB	Output is correct
18	Incorrect	446 ms	26624 KB	the output code does not encode the input sequence
19	Correct	2122 ms	58676 KB	Output is correct
20	Correct	1911 ms	58644 KB	Output is correct