Submission #137740

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137740	2019-07-28T09:18:57 Z	김현수(#3360)	RLE (BOI06_rle)	C++14	15 / 100	1373 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

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1400 KB	Output is correct
2	Incorrect	3 ms	1400 KB	the output code does not encode the input sequence
3	Incorrect	3 ms	1400 KB	the output code does not encode the input sequence
4	Incorrect	4 ms	1400 KB	the output code does not encode the input sequence
5	Incorrect	4 ms	1400 KB	the output code does not encode the input sequence
6	Incorrect	24 ms	2264 KB	the output code does not encode the input sequence
7	Incorrect	170 ms	7684 KB	the output code does not encode the input sequence
8	Incorrect	226 ms	10128 KB	the output code does not encode the input sequence
9	Incorrect	399 ms	18608 KB	Unexpected end of file - int32 expected
10	Incorrect	169 ms	7444 KB	Unexpected end of file - int32 expected
11	Incorrect	140 ms	7140 KB	the output code does not encode the input sequence
12	Incorrect	332 ms	15508 KB	the output code does not encode the input sequence
13	Incorrect	371 ms	16448 KB	the output code does not encode the input sequence
14	Incorrect	167 ms	7488 KB	the output code does not encode the input sequence
15	Incorrect	91 ms	4588 KB	the output code does not encode the input sequence
16	Incorrect	362 ms	17072 KB	the output code does not encode the input sequence
17	Incorrect	466 ms	19920 KB	the output code does not encode the input sequence
18	Runtime error	1245 ms	524292 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Correct	1270 ms	45504 KB	Output is correct
20	Correct	1373 ms	45520 KB	Output is correct