oj.uz

답안 #137794

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137794 2019-07-28T09:44:30 Z 윤교준(#3280) RLE (BOI06_rle) C++14
90 / 100
 2500 ms 136088 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*4], dmn[MAXN*4];
	pii di[MAXN*4];
	int dmni[MAXN*4];

	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 pvi[MAXN];
int sigDel(int c, int x) {
	int &i = pvi[c];
	for(int n = sz(SDel[c]); i+1 < n && SDel[c][i+1].first < x; i++);
	return SDel[c][i].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:302: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 8184 KB Output is correct
2 Correct 11 ms 8312 KB Output is correct
3 Correct 9 ms 8316 KB Output is correct
4 Correct 9 ms 8312 KB Output is correct
5 Correct 9 ms 8440 KB Output is correct
6 Correct 25 ms 10512 KB Output is correct
7 Correct 133 ms 22660 KB Output is correct
8 Correct 172 ms 30080 KB Output is correct
9 Correct 314 ms 64516 KB Output is correct
10 Correct 128 ms 21528 KB Output is correct
11 Correct 113 ms 22388 KB Output is correct
12 Correct 287 ms 53348 KB Output is correct
13 Correct 285 ms 40860 KB Output is correct
14 Correct 165 ms 27320 KB Output is correct
15 Correct 105 ms 18648 KB Output is correct
16 Correct 270 ms 40476 KB Output is correct
17 Correct 413 ms 53984 KB Output is correct
18 Correct 619 ms 62740 KB Output is correct
19 Execution timed out 2529 ms 134324 KB Time limit exceeded
20 Execution timed out 2536 ms 136088 KB Time limit exceeded