Submission #137621

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137621	2019-07-28T07:39:25 Z	임유진(#3281)	RLE (BOI06_rle)	C++14	95 / 100	2500 ms	84448 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(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), 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	380 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	508 KB	Output is correct
6	Correct	23 ms	2676 KB	Output is correct
7	Correct	166 ms	16324 KB	Output is correct
8	Correct	223 ms	22496 KB	Output is correct
9	Correct	413 ms	46264 KB	Output is correct
10	Correct	158 ms	16736 KB	Output is correct
11	Correct	142 ms	12776 KB	Output is correct
12	Correct	359 ms	32196 KB	Output is correct
13	Correct	364 ms	36144 KB	Output is correct
14	Correct	173 ms	13800 KB	Output is correct
15	Correct	97 ms	7664 KB	Output is correct
16	Correct	350 ms	37852 KB	Output is correct
17	Correct	486 ms	45524 KB	Output is correct
18	Correct	610 ms	49588 KB	Output is correct
19	Execution timed out	2555 ms	79544 KB	Time limit exceeded
20	Correct	2304 ms	84448 KB	Output is correct