oj.uz

Submission #137624

# Submission time Handle Problem Language Result Execution time Memory
137624 2019-07-28T07:41:17 Z 윤교준(#3280) RLE (BOI06_rle) C++14
5 / 100
 380 ms 47488 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 C[MAXK], D[MAXK];

int N, K;

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;
	}
}

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;

	if(ll(K)*K > 40000000) return -1;

	runNoChange();
	runNoAlphabet();

	Ans.prt();
	return 0;
}

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory 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 504 KB code is not the shortest
5 Incorrect 3 ms 504 KB code is not the shortest
6 Runtime error 12 ms 1524 KB Execution failed because the return code was nonzero
7 Runtime error 80 ms 8044 KB Execution failed because the return code was nonzero
8 Runtime error 109 ms 9452 KB Execution failed because the return code was nonzero
9 Runtime error 193 ms 26308 KB Execution failed because the return code was nonzero
10 Runtime error 78 ms 8428 KB Execution failed because the return code was nonzero
11 Runtime error 68 ms 5480 KB Execution failed because the return code was nonzero
12 Runtime error 124 ms 17624 KB Execution failed because the return code was nonzero
13 Runtime error 170 ms 16080 KB Execution failed because the return code was nonzero
14 Runtime error 56 ms 7276 KB Execution failed because the return code was nonzero
15 Runtime error 30 ms 3948 KB Execution failed because the return code was nonzero
16 Correct 380 ms 33220 KB Output is correct
17 Runtime error 192 ms 18136 KB Execution failed because the return code was nonzero
18 Runtime error 198 ms 18396 KB Execution failed because the return code was nonzero
19 Runtime error 279 ms 47456 KB Execution failed because the return code was nonzero
20 Runtime error 279 ms 47488 KB Execution failed because the return code was nonzero