답안 #137771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137771 2019-07-28T09:32:02 Z khsoo01 RLE (BOI06_rle) C++11
100 / 100
1493 ms 53328 KB
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 2000005, L = 131072, inf = 1e9;

int m, n, rn, a[N], sw[N], crm;
ll c[N];

vector<int> ans;

void append (int V, ll C) {
	if(!rn || a[rn] != V) rn++;
	a[rn] = V;
	c[rn] += C;
}

int cost1 (ll L) {return (L+m-1)/m*3;}

void make1 (ll L) {
	while(L) {
		int C = min(m-1ll, L-1);
		ans.push_back(C);
		ans.push_back(crm);
		ans.push_back(crm);
		L -= C+1;
	}
}

int cost2 (ll L) {
	int R = L%(m+2);
	if(R == 0 || R > 2) return (L+m+1)/(m+2)*3;
	else return L/(m+2)*3+R;
}

void make2 (ll L, int I) {
	while(L > 3) {
		int C = min(m-1ll, L-3);
		ans.push_back(C);
		ans.push_back(I);
		ans.push_back(crm);
		L -= C + 3;
	}
	while(L) {
		ans.push_back(I);
		L--;
	}
}

void swit (int I) {
	ans.push_back(0);
	ans.push_back(crm);
	ans.push_back(I);
	crm = I;
}

struct segtree {
	pii v[2*L];
	void init () {
		for(int i=1;i<m;i++) {
			v[i+L] = {3, i};
		}
		for(int i=L;--i;) {
			v[i] = min(v[2*i], v[2*i+1]);
		}
	}
	void upd (int P, int V) {
		P += L; v[P].X += V; P /= 2;
		while(P) {
			v[P] = min(v[2*P], v[2*P+1]);
			P /= 2;
		}
	}
	pii get (int S, int E) {
		S += L; E += L;
		pii R = {inf, inf};
		while(S <= E) {
			if(S%2 == 1) R = min(R, v[S++]);
			if(E%2 == 0) R = min(R, v[E--]);
			S /= 2; E /= 2;
		}
		return R;
	}
} seg;

int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++) {
		int T;
		scanf("%d",&T);
		if(T != crm) {
			append(T, 1);
			continue;
		}
		i += 2;
		int A, B;
		scanf("%d%d",&A,&B);
		if(T == A) append(A, B+1);
		else if(B) append(A, B+3);
		else crm = A;
	}
	seg.init();
	for(int i=1;i<=rn;i++) {
		int X = cost1(c[i]) - cost2(c[i]);
		auto V1 = min(seg.get(0, a[i]-1), seg.get(a[i]+1, m-1)), V2 = seg.get(a[i], a[i]);
		if(X > V1.X - V2.X + 3) {
			seg.upd(a[i], V1.X - V2.X + 3);
			sw[i] = V1.Y;
		}
		else {
			seg.upd(a[i], X);
			sw[i] = -1;
		}
	}
	crm = seg.get(0, m-1).Y;
	for(int i=rn;i>=1;i--) {
		if(crm == a[i] && ~sw[i]) swit(sw[i]);
		if(crm == a[i]) make1(c[i]);
		else make2(c[i], a[i]);
	}
	if(crm != 0) swit(0);
	printf("%d\n", ans.size());
	for(int i=ans.size();i--;) {
		printf("%d ", ans[i]);
	}
}

Compilation message

rle.cpp: In function 'int main()':
rle.cpp:126:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", ans.size());
                 ~~~~~~~~~~^
rle.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&m,&n);
  ~~~~~^~~~~~~~~~~~~~
rle.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&T);
   ~~~~~^~~~~~~~~
rle.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
   ~~~~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 3 ms 1400 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 4 ms 1372 KB Output is correct
5 Correct 4 ms 1400 KB Output is correct
6 Correct 25 ms 2436 KB Output is correct
7 Correct 171 ms 7896 KB Output is correct
8 Correct 227 ms 10336 KB Output is correct
9 Correct 439 ms 21180 KB Output is correct
10 Correct 169 ms 7644 KB Output is correct
11 Correct 141 ms 7360 KB Output is correct
12 Correct 352 ms 17640 KB Output is correct
13 Correct 370 ms 16824 KB Output is correct
14 Correct 174 ms 8336 KB Output is correct
15 Correct 93 ms 5100 KB Output is correct
16 Correct 356 ms 17232 KB Output is correct
17 Correct 483 ms 21180 KB Output is correct
18 Correct 509 ms 22352 KB Output is correct
19 Correct 1376 ms 53260 KB Output is correct
20 Correct 1493 ms 53328 KB Output is correct