oj.uz

답안 #137785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137785 2019-07-28T09:39:15 Z 윤교준(#3280) RLE (BOI06_rle) C++14
90 / 100
 2500 ms 161180 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 7544 KB Output is correct
4 Correct 9 ms 7544 KB Output is correct
5 Correct 9 ms 7544 KB Output is correct
6 Correct 25 ms 9616 KB Output is correct
7 Correct 134 ms 21944 KB Output is correct
8 Correct 185 ms 29268 KB Output is correct
9 Correct 388 ms 63936 KB Output is correct
10 Correct 130 ms 20708 KB Output is correct
11 Correct 113 ms 21576 KB Output is correct
12 Correct 330 ms 52528 KB Output is correct
13 Correct 289 ms 40088 KB Output is correct
14 Correct 176 ms 26424 KB Output is correct
15 Correct 105 ms 17784 KB Output is correct
16 Correct 266 ms 39536 KB Output is correct
17 Correct 420 ms 52968 KB Output is correct
18 Correct 594 ms 61768 KB Output is correct
19 Execution timed out 2545 ms 161180 KB Time limit exceeded
20 Execution timed out 2540 ms 134924 KB Time limit exceeded