oj.uz

답안 #137787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137787 2019-07-28T09:41:27 Z 윤교준(#3280) RLE (BOI06_rle) C++14
90 / 100
 2500 ms 135284 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);
	vector<int> AV;
	auto upd = [&](int i, int c, int j, int t) {
		if(dp[i] <= t) return;
		dp[i] = t;
		bfi[i] = j;
		bfc[i] = c;
	};
	for(int i = 0;; i++) {
		AV.clear();
		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;
		for(int a : AV) upd(i, 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(i, 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; 0 < i;) {
		ni = max(0, 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:297: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 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 9 ms 7544 KB Output is correct
6 Correct 26 ms 9616 KB Output is correct
7 Correct 136 ms 21892 KB Output is correct
8 Correct 175 ms 29240 KB Output is correct
9 Correct 392 ms 63852 KB Output is correct
10 Correct 131 ms 20708 KB Output is correct
11 Correct 116 ms 21572 KB Output is correct
12 Correct 337 ms 52436 KB Output is correct
13 Correct 296 ms 40076 KB Output is correct
14 Correct 178 ms 26484 KB Output is correct
15 Correct 108 ms 17744 KB Output is correct
16 Correct 265 ms 39612 KB Output is correct
17 Correct 426 ms 52964 KB Output is correct
18 Correct 601 ms 61676 KB Output is correct
19 Execution timed out 2528 ms 135284 KB Time limit exceeded
20 Execution timed out 2553 ms 134304 KB Time limit exceeded