oj.uz

답안 #137602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137602 2019-07-28T07:20:47 Z 윤교준(#3280) RLE (BOI06_rle) C++14
0 / 100
 535 ms 43988 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 100055;
const int MAXK = 2000055;

struct SOL {
	SOL() : n(0) {}
	vector<int> V;
	int n;

	void push(int x) { V.eb(x); n++; }
	void prt() const {
		cout << n << '\n';
		for(int v : V) cout << v << ' ';
		cout << '\n';
	}
	bool operator < (const SOL &t) const {
		return n < t.n;
	}
} Ans;

int A[MAXK], B[MAXK];

int N, K;

void runNoChange() {
	SOL sol;
	for(int i = 0; i < K; i++) {
		if(!A[i]) {
			int k = B[i];
			for(int t; k;) {
				t = min(N, k);
				sol.push(0);
				sol.push(0);
				sol.push(t-1);
				k -= t;
			}
		} else {
			int c = A[i], k = B[i];
			for(int t; k;) {
				if(k < 3) {
					sol.push(c);
					k--;
					continue;
				}
				t = min(N+2, k);
				sol.push(0);
				sol.push(c);
				sol.push(t-3);
				k -= t;
			}
		}
	}
	if(sol < Ans) swap(Ans, sol);
}

void runNoAlphabet() {
	bitset<MAXN> chk;
	for(int i = 0; i < K; i++) chk[A[i]] = true;
	int x = 1; for(; x < N && chk[x]; x++);
	if(x == N) return;

	SOL sol;
	sol.push(0); sol.push(x); sol.push(0);
	for(int i = 0; i < K; i++) {
		int c = A[i], k = B[i];
		for(int t; k;) {
			if(k < 3) {
				sol.push(c);
				k--;
				continue;
			}
			t = min(N+2, k);
			sol.push(x);
			sol.push(c);
			sol.push(t-3);
			k -= t;
		}
	}
	if(sol < Ans) swap(Ans, sol);
}

void input() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int L; cin >> N >> L;
	vector<pii> T;
	vector<int> V(L);
	for(int i = 0; i < L; i++) cin >> V[i];
	for(int i = 0, x = 0; i < L;) {
		if(V[i] != x) {
			T.eb(V[i], 1);
			i++;
		} else if(x == V[i+1]) {
			T.eb(x, V[i+2]+1);
			i += 3;
		} else if(!V[i+2]) {
			x = V[i+1];
			i += 3;
		} else {
			T.eb(V[i+1], V[i+2]+3);
			i += 3;
		}
	}
	for(auto &v : T) {
		int a, b; tie(a, b) = v;
		if(K && A[K-1] == a) B[K-1] += b;
		else {
			A[K] = a; B[K] = b;
			K++;
		}
	}
}

int main() {
	input();
	Ans.n = INF;

	runNoChange();
	runNoAlphabet();

	Ans.prt();
	return 0;
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB code is not the shortest
2 Incorrect 2 ms 376 KB the output code does not encode the input sequence
3 Incorrect 2 ms 376 KB the output code does not encode the input sequence
4 Incorrect 3 ms 504 KB the output code does not encode the input sequence
5 Incorrect 2 ms 376 KB the output code does not encode the input sequence
6 Incorrect 21 ms 1684 KB the output code does not encode the input sequence
7 Incorrect 152 ms 10388 KB the output code does not encode the input sequence
8 Incorrect 214 ms 16800 KB the output code does not encode the input sequence
9 Incorrect 337 ms 24664 KB the output code does not encode the input sequence
10 Incorrect 156 ms 10640 KB the output code does not encode the input sequence
11 Incorrect 127 ms 9544 KB the output code does not encode the input sequence
12 Incorrect 233 ms 19864 KB the output code does not encode the input sequence
13 Incorrect 322 ms 22292 KB the output code does not encode the input sequence
14 Incorrect 97 ms 7364 KB the output code does not encode the input sequence
15 Incorrect 51 ms 3856 KB the output code does not encode the input sequence
16 Incorrect 384 ms 33192 KB the output code does not encode the input sequence
17 Incorrect 369 ms 25156 KB the output code does not encode the input sequence
18 Incorrect 535 ms 30256 KB Output is corrupted
19 Incorrect 454 ms 43988 KB code is not the shortest
20 Incorrect 475 ms 43864 KB code is not the shortest