Submission #137759

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137759	2019-07-28T09:27:17 Z	김현수(#3360)	RLE (BOI06_rle)	C++14	95 / 100	1385 ms	524292 KB

rle

#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);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1

95.0 / 100.0

#	Verdict	Execution time	Memory	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