oj.uz

답안 #137778

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137778 2019-07-28T09:36:38 Z 윤교준(#3280) RLE (BOI06_rle) C++14
90 / 100
 2500 ms 134112 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#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<ll, int> pli;
typedef pair<int, ll> pil;
static unsigned char str[22000022], *p=str;

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;

struct SEG {
	int dp[MAXN*3], dmn[MAXN*3];
	pii di[MAXN*3];
	int dmni[MAXN*3];

	void init(int i, int s, int e) {
		dp[i] = dmn[i] = INF;
		di[i] = {s, -1};
		dmni[i] = -1;
		if(s == e) return;
		int m = (s+e) >> 1;
		init(i<<1, s, m);
		init(i<<1|1, m+1, e);
	}

	void prop(int i, int s, int e) {
		if(INF <= dmn[i]) return;
		if(dmn[i] < dp[i]) {
			dp[i] = dmn[i];
			di[i] = {s, dmni[i]};
		}
		if(s != e) {
			if(dmn[i] < dmn[i<<1]) {
				dmn[i<<1] = dmn[i];
				dmni[i<<1] = dmni[i];
			}
			if(dmn[i] < dmn[i<<1|1]) {
				dmn[i<<1|1] = dmn[i];
				dmni[i<<1|1] = dmni[i];
			}
		}
		dmn[i] = INF;
	}
	void cal(int i) {
		int j = dp[i<<1] < dp[i<<1|1] ? (i<<1) : (i<<1|1);
		dp[i] = dp[j];
		di[i] = di[j];
	}

	void upd(int i, int s, int e, int x, ll r) {
		prop(i, s, e); if(x < s || e < x) return;
		if(s == e) {
			dp[i] += r;
			return;
		}
		int m = (s+e) >> 1;
		upd(i<<1, s, m, x, r);
		upd(i<<1|1, m+1, e, x, r);
		cal(i);
	}
	void upd(int i, int s, int e, int p, int q, int x, ll r) {
		prop(i, s, e); if(q < p || e < p || q < s) return;
		if(p <= s && e <= q) {
			dmn[i] = r;
			dmni[i] = x;
			prop(i, s, e);
			return;
		}
		int m = (s+e) >> 1;
		upd(i<<1, s, m, p, q, r);
		upd(i<<1|1, m+1, e, p, q, r);
		cal(i);
	}
	void upd(int i, int s, int e, int x, int y, ll r) {
		prop(i, s, e); if(x < s || e < x) return;
		if(s == e) {
			dp[i] = r;
			di[i] = {x, y};
			return;
		}
		int m = (s+e) >> 1;
		upd(i<<1, s, m, x, y, r);
		upd(i<<1|1, m+1, e, x, y, r);
		cal(i);
	}
	pair<int, pii> get(int i, int s, int e, int p, int q) {
		prop(i, s, e); if(q < p || e < p || q < s) return {INF, {-1, -1}};
		if(p <= s && e <= q) return {dp[i], di[i]};
		int m = (s+e) >> 1;
		auto ret = min(get(i<<1, s, m, p, q), get(i<<1|1, m+1, e, p, q));
		cal(i);
		return ret;
	}
} seg;

vector<pii> SDel[MAXN];
vector<int> AI[MAXN];
int dp[MAXK], bfi[MAXK], bfc[MAXK];

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

int N, K;

void makeSeq(const vector<int>&);
int sigDel(int c, int x) { return prev(lower_bound(allv(SDel[c]), pii(x, -INF))) -> second; }

void process() {
	seg.init(1, 0, N-1);
	for(int i = 0;; i++) {
		vector<int> AV;
		if(i < K) {
			AV.eb(0);
			if(A[i]) AV.eb(A[i]);
		}
		else for(int j = 0; j < N; j++) AV.eb(j);
		dp[i] = INF;
		auto upd = [&](int c, int j, int t) {
			if(dp[i] <= t) return;
			dp[i] = t;
			bfi[i] = j;
			bfc[i] = c;
		};
		for(int a : AV) upd(a, 0, sigDel(a, i) - 3*(a ? (i-1) : i));
		pair<int, pii> ret = seg.get(1, 0, N-1, 0, N-1);
		if(ret.first < INF) {
			ret.first -= 3*i;
			upd(ret.second.first, ret.second.second, ret.first);
		}

		if(i == K) break;
		seg.upd(1, 0, N-1, 0, N-1, i, dp[i] + 3*i + 3);
		seg.upd(1, 0, N-1, A[i], Del[i]);
	}

	vector<int> V;
	for(int i = K, ni, nc; i;) {
		ni = bfi[i]; nc = bfc[i];
		for(; ni < i; i--) V.eb(nc);
	}
	revv(V);
	makeSeq(V);
}

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 precal() {
	for(int i = 0; i < N; i++) SDel[i].eb(-1, 0);
	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];

		AI[A[i]].eb(i);
		SDel[A[i]].eb(i, SDel[A[i]].back().second + Del[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() {
	fread(str, 1, 22000022, stdin);
	int L; rf(N) rf(L)
	vector<pii> T;
	vector<int> V(L);
	for(int i = 0; i < L; i++) { rf(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;
}

Compilation message

rle.cpp: In function 'void input()':
rle.cpp:296:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 22000022, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
90.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 10 ms 7416 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 8 ms 7548 KB Output is correct
5 Correct 9 ms 7544 KB Output is correct
6 Correct 26 ms 9620 KB Output is correct
7 Correct 138 ms 21900 KB Output is correct
8 Correct 182 ms 29212 KB Output is correct
9 Correct 432 ms 63756 KB Output is correct
10 Correct 132 ms 20712 KB Output is correct
11 Correct 121 ms 21836 KB Output is correct
12 Correct 383 ms 52380 KB Output is correct
13 Correct 323 ms 40084 KB Output is correct
14 Correct 205 ms 26460 KB Output is correct
15 Correct 119 ms 17800 KB Output is correct
16 Correct 263 ms 39636 KB Output is correct
17 Correct 508 ms 52968 KB Output is correct
18 Correct 634 ms 61528 KB Output is correct
19 Execution timed out 2556 ms 134112 KB Time limit exceeded
20 Execution timed out 2568 ms 132236 KB Time limit exceeded