Submission #137616

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137616	2019-07-28T07:35:01 Z	임유진(#3281)	RLE (BOI06_rle)	C++14	95 / 100	2409 ms	61028 KB

rle

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

typedef long long lint;
typedef __int128_t llint;
typedef pair<llint, int> plli;

#define fi first
#define se second

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

int inp[MAXM];
int num[MAXM], cnt[MAXM], nn;
llint 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<plli> 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	500 KB	Output is correct
5	Correct	3 ms	436 KB	Output is correct
6	Correct	22 ms	2040 KB	Output is correct
7	Correct	159 ms	12392 KB	Output is correct
8	Correct	219 ms	17292 KB	Output is correct
9	Correct	375 ms	30564 KB	Output is correct
10	Correct	157 ms	12804 KB	Output is correct
11	Correct	135 ms	10080 KB	Output is correct
12	Correct	329 ms	21964 KB	Output is correct
13	Correct	349 ms	27596 KB	Output is correct
14	Correct	168 ms	9708 KB	Output is correct
15	Correct	91 ms	5612 KB	Output is correct
16	Correct	341 ms	29964 KB	Output is correct
17	Correct	458 ms	34040 KB	Output is correct
18	Incorrect	477 ms	28188 KB	the output code does not encode the input sequence
19	Correct	2409 ms	60940 KB	Output is correct
20	Correct	2156 ms	61028 KB	Output is correct