Submission #137631

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137631	2019-07-28T07:45:17 Z	임유진(#3281)	RLE (BOI06_rle)	C++14	95 / 100	2500 ms	84296 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], nn;
llint cnt[MAXM];
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(llint(0), i));
	for(int i = nn - 1; i >= 0; i--) {
		llint p = ((cnt[i] - 1) / N + 1) * 3;
		llint q = cnt[i] / (N + 2) * 3 + min(cnt[i] % (N + 2), llint(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(llint(N), cnt[i]) - 1);
					cnt[i] -= min(llint(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	24 ms	2676 KB	Output is correct
7	Correct	167 ms	16284 KB	Output is correct
8	Correct	222 ms	22668 KB	Output is correct
9	Correct	421 ms	46156 KB	Output is correct
10	Correct	168 ms	16736 KB	Output is correct
11	Correct	139 ms	12768 KB	Output is correct
12	Correct	364 ms	32212 KB	Output is correct
13	Correct	360 ms	35924 KB	Output is correct
14	Correct	171 ms	13672 KB	Output is correct
15	Correct	97 ms	7580 KB	Output is correct
16	Correct	352 ms	37840 KB	Output is correct
17	Correct	475 ms	45352 KB	Output is correct
18	Correct	607 ms	49472 KB	Output is correct
19	Execution timed out	2525 ms	80060 KB	Time limit exceeded
20	Correct	2389 ms	84296 KB	Output is correct