Submission #137634

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137634	2019-07-28T07:49:22 Z	임유진(#3281)	RLE (BOI06_rle)	C++14	100 / 100	2282 ms	66528 KB

rle

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

typedef long long lint;
//typedef __int128_t llint;
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], nn;
lint cnt[MAXM];
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--) {
		lint p = ((cnt[i] - 1) / N + 1) * 3;
		lint q = cnt[i] / (N + 2) * 3 + min(cnt[i] % (N + 2), 3ll);
		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(lint(N), cnt[i]) - 1);
					cnt[i] -= min(lint(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

100.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	376 KB	Output is correct
6	Correct	22 ms	2168 KB	Output is correct
7	Correct	167 ms	13764 KB	Output is correct
8	Correct	218 ms	19024 KB	Output is correct
9	Correct	381 ms	35700 KB	Output is correct
10	Correct	155 ms	14128 KB	Output is correct
11	Correct	139 ms	11104 KB	Output is correct
12	Correct	341 ms	25376 KB	Output is correct
13	Correct	377 ms	30548 KB	Output is correct
14	Correct	161 ms	10980 KB	Output is correct
15	Correct	90 ms	6124 KB	Output is correct
16	Correct	355 ms	32464 KB	Output is correct
17	Correct	462 ms	37740 KB	Output is correct
18	Correct	579 ms	40748 KB	Output is correct
19	Correct	2282 ms	66264 KB	Output is correct
20	Correct	2198 ms	66528 KB	Output is correct