답안 #137759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137759 2019-07-28T09:27:17 Z 김현수(#3360) RLE (BOI06_rle) C++14
95 / 100
1385 ms 524292 KB
#include<bits/stdc++.h>
#define X first
#define Y second
#define pii MyFuckingPair
using namespace std;

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

int m, n, rn, a[N], c[N], sw[N], crm;
vector<int> ans;

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

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

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

int cost2 (int 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 (int L, int I) {
	while(L > 3) {
		int C = min(m-1, 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 MyFuckingPair {
	int X, Y;
	bool operator < (const MyFuckingPair &T) const {
		if(X != T.X) return X < T.X;
		return Y < T.Y;
	}
};

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:132: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:97: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:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&T);
   ~~~~~^~~~~~~~~
rle.cpp:107: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 1400 KB Output is correct
5 Correct 4 ms 1400 KB Output is correct
6 Correct 24 ms 2292 KB Output is correct
7 Correct 172 ms 7644 KB Output is correct
8 Correct 227 ms 10196 KB Output is correct
9 Correct 394 ms 18588 KB Output is correct
10 Correct 173 ms 7504 KB Output is correct
11 Correct 139 ms 7100 KB Output is correct
12 Correct 330 ms 15452 KB Output is correct
13 Correct 367 ms 16236 KB Output is correct
14 Correct 198 ms 7588 KB Output is correct
15 Correct 88 ms 4680 KB Output is correct
16 Correct 358 ms 17140 KB Output is correct
17 Correct 463 ms 20444 KB Output is correct
18 Runtime error 1233 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Correct 1259 ms 45496 KB Output is correct
20 Correct 1385 ms 45612 KB Output is correct