oj.uz

답안 #137609

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137609 2019-07-28T07:28:45 Z 윤교준(#3280) RLE (BOI06_rle) C++14
5 / 100
 497 ms 51752 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;
typedef pair<int, ll> pil;

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

struct SOL {
	SOL() : V(), 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]; ll B[MAXK];

int N, K;

void runNoChange() {
	SOL sol;
	for(int i = 0; i < K; i++) {
		if(!A[i]) {
			ll k = B[i];
			for(ll t; k;) {
				t = min(ll(N), k);
				sol.push(0);
				sol.push(0);
				sol.push(t-1);
				k -= t;
			}
		} else {
			int c = A[i]; ll k = B[i];
			for(ll t; k;) {
				if(k < 4) {
					sol.push(c);
					k--;
					continue;
				}
				t = min(ll(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]; ll k = B[i];
		for(int t; k;) {
			if(k < 4) {
				sol.push(c);
				k--;
				continue;
			}
			t = min(ll(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
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB code is not the shortest
2 Incorrect 2 ms 376 KB code is not the shortest
3 Incorrect 2 ms 376 KB code is not the shortest
4 Incorrect 3 ms 376 KB code is not the shortest
5 Incorrect 2 ms 376 KB code is not the shortest
6 Incorrect 21 ms 1688 KB code is not the shortest
7 Incorrect 163 ms 10620 KB code is not the shortest
8 Incorrect 221 ms 16928 KB code is not the shortest
9 Incorrect 335 ms 26308 KB code is not the shortest
10 Incorrect 160 ms 10608 KB code is not the shortest
11 Incorrect 126 ms 9824 KB code is not the shortest
12 Incorrect 223 ms 21916 KB code is not the shortest
13 Incorrect 325 ms 22684 KB code is not the shortest
14 Incorrect 96 ms 8252 KB code is not the shortest
15 Incorrect 50 ms 4500 KB code is not the shortest
16 Correct 381 ms 33316 KB Output is correct
17 Incorrect 364 ms 26552 KB code is not the shortest
18 Incorrect 366 ms 27440 KB code is not the shortest
19 Incorrect 497 ms 51752 KB code is not the shortest
20 Incorrect 462 ms 51748 KB code is not the shortest