Submission #137589

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137589	2019-07-28T07:07:04 Z	임유진(#3281)	RLE (BOI06_rle)	C++14	0 / 100	440 ms	30852 KB

rle

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

typedef pair<int, int> pii;

#define fi first
#define se second

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

int inp[MAXM];
int num[MAXM], cnt[MAXM], nn;
int 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<pii> s;
	for(int i = 0; i < N; i++) s.insert(make_pair(0, i));
	for(int i = nn - 1; i >= 0; i--) if(cnt[i] < 3) {
		s.erase(make_pair(dp[num[i]], num[i]));
		if(dp[num[i]] + 3 - cnt[i] < s.begin() -> fi + 3) {
			dp[num[i]] += 3 - cnt[i];
			w[i] = num[i];
			s.insert(make_pair(dp[num[i]], num[i]));
		}
		else {
			dp[num[i]] = s.begin() -> fi + 3;
			w[i] = s.begin() -> se;
			s.insert(make_pair(dp[num[i]], w[i]));
		}
	}

	e = 0;
	for(int i = 0; i < nn; i++) {
		if(num[i] != e) {
			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);
			}
		}
		else {
			if(cnt[i] >= 3 || w[i] == num[i]) {
				ans.push_back(e);
				ans.push_back(e);
				ans.push_back(cnt[i] - 1);
			}
			else {
				ans.push_back(e);
				ans.push_back(w[i]);
				ans.push_back(0);
				e = w[i];
				for(int j = 0; j < cnt[i]; j++) ans.push_back(num[i]);
			}
		}
	}

	cout << ans.size() << "\n";
	for(auto a : ans) cout << a << " ";
	return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	380 KB	Output is corrupted
2	Incorrect	2 ms	376 KB	Output is corrupted
3	Incorrect	2 ms	376 KB	Output is corrupted
4	Incorrect	2 ms	380 KB	Output is corrupted
5	Incorrect	3 ms	504 KB	Output is corrupted
6	Incorrect	15 ms	1656 KB	Output is corrupted
7	Incorrect	85 ms	7412 KB	Output is corrupted
8	Incorrect	111 ms	9844 KB	Output is corrupted
9	Incorrect	189 ms	19320 KB	the output code does not encode the input sequence
10	Incorrect	79 ms	7544 KB	Output is corrupted
11	Incorrect	78 ms	6180 KB	Output is corrupted
12	Incorrect	226 ms	20788 KB	Output is corrupted
13	Incorrect	173 ms	14972 KB	Output is corrupted
14	Incorrect	97 ms	9444 KB	Output is corrupted
15	Incorrect	56 ms	5356 KB	Output is corrupted
16	Incorrect	175 ms	13928 KB	Output is corrupted
17	Incorrect	240 ms	21404 KB	Output is corrupted
18	Incorrect	335 ms	25052 KB	Output is corrupted
19	Incorrect	439 ms	30852 KB	the output code does not encode the input sequence
20	Incorrect	440 ms	29000 KB	the output code does not encode the input sequence