답안 #137611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137611	2019-07-28T07:31:53 Z	임유진(#3281)	RLE (BOI06_rle)	C++14	65 / 100	1670 ms	39000 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[MAXN];
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

65.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	380 KB	Output is correct
4	Correct	3 ms	504 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	22 ms	2036 KB	Output is correct
7	Correct	158 ms	12384 KB	Output is correct
8	Correct	221 ms	17280 KB	Output is correct
9	Incorrect	225 ms	19704 KB	the output code does not encode the input sequence
10	Correct	163 ms	12772 KB	Output is correct
11	Correct	134 ms	10080 KB	Output is correct
12	Incorrect	207 ms	12920 KB	the output code does not encode the input sequence
13	Correct	340 ms	27508 KB	Output is correct
14	Incorrect	153 ms	9588 KB	code is not the shortest
15	Correct	85 ms	5484 KB	Output is correct
16	Correct	345 ms	29828 KB	Output is correct
17	Incorrect	454 ms	33752 KB	code is not the shortest
18	Incorrect	473 ms	28516 KB	the output code does not encode the input sequence
19	Incorrect	1670 ms	39000 KB	the output code does not encode the input sequence
20	Incorrect	1669 ms	31936 KB	the output code does not encode the input sequence