oj.uz

Submission #137654

# Submission time Handle Problem Language Result Execution time Memory
137654 2019-07-28T08:17:16 Z 윤교준(#3280) RLE (BOI06_rle) C++14
85 / 100
 948 ms 311536 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 revv(V) reverse(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 **dp, **dpi;

int A[MAXK]; ll B[MAXK];
int C[MAXK], D[MAXK], Del[MAXK];
ll SDel[MAXK];

int N, K;

void makeSeq(const vector<int> &XV) {
	SOL sol;
	for(int i = 0, x = 0, y; i < K; i++) {
		y = XV[i];
		if(x != y) {
			sol.push(x);
			sol.push(y);
			sol.push(0);
			x = y;
		}
		if(x == A[i]) {
			ll k = B[i];
			for(ll t; k;) {
				t = min(ll(N), k);
				sol.push(x);
				sol.push(x);
				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(x);
				sol.push(c);
				sol.push(t-3);
				k -= t;
			}
		}
	}
	if(sol < Ans) swap(Ans, sol);
}

void process() {
	for(int i = 0; i < K; i++) SDel[A[i]] += Del[i];
	vector<int> AV;
	for(int i = 0; i < N; i++) AV.eb(i);
	sort(AV.begin()+1, AV.end(), [&](int a, int b) {
		return SDel[a] < SDel[b];
	});
	int L = min(N, 20000000 / K);
	if(L < sz(AV)) AV.resize(L);

	dp = new int*[K+1];
	dpi = new int*[K+1];
	for(int i = 0; i <= K; i++) {
		dp[i] = new int[L];
		fill(dp[i], dp[i]+L, INF);
		dpi[i] = new int[L];
	}
	dp[0][0] = 0;
	for(int i = 0; i < K; i++) {
		int totmni = int(min_element(dp[i], dp[i]+L) - dp[i]);
		int totmn = dp[i][totmni];
		for(int j = 0; j < L; j++) {
			if(totmn < dp[i][j]-3) {
				dp[i+1][j] = totmn;
				dpi[i+1][j] = totmni;
			} else {
				dp[i+1][j] = dp[i][j]-3;
				dpi[i+1][j] = j;
			}
			if(AV[j] == A[i]) dp[i+1][j] += Del[i];
		}
	}

	vector<int> V;
	int j = int(min_element(dp[K], dp[K]+L) - dp[K]);
	for(int i = K; i--;) {
		V.eb(AV[j]);
		j = dpi[i+1][j];
	}
	revv(V);

	makeSeq(V);
}

void precal() {
	for(int i = 0; i < K; i++) {
		ll k = B[i], ret = 0;
		for(ll t; k;) {
			if(k < 4) {
				ret += k;
				break;
			}
			t = min(ll(N+2), k);
			ret += 3;
			k -= t;
		}
		C[i] = ret;
		k = B[i]; ret = 0;
		for(ll t; k;) {
			t = min(ll(N), k);
			ret += 3;
			k -= t;
		}
		D[i] = ret;
		Del[i] = D[i] - C[i];
	}
}

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();
	precal();
	Ans.n = INF;

	runNoChange();
	runNoAlphabet();

	process();

	Ans.prt();
	return 0;
}

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 376 KB Output is correct
2 Correct 2 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 1016 KB Output is correct
6 Correct 26 ms 3620 KB Output is correct
7 Correct 175 ms 21380 KB Output is correct
8 Correct 246 ms 31520 KB Output is correct
9 Correct 475 ms 94408 KB Output is correct
10 Correct 167 ms 17768 KB Output is correct
11 Correct 270 ms 91852 KB Output is correct
12 Correct 566 ms 209620 KB Output is correct
13 Correct 522 ms 120200 KB Output is correct
14 Incorrect 382 ms 179260 KB code is not the shortest
15 Incorrect 330 ms 168332 KB code is not the shortest
16 Correct 430 ms 53672 KB Output is correct
17 Correct 683 ms 205640 KB Output is correct
18 Correct 699 ms 210592 KB Output is correct
19 Correct 925 ms 311536 KB Output is correct
20 Incorrect 948 ms 311408 KB code is not the shortest