Submission #137702

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137702	2019-07-28T08:45:11 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	40 / 100	628 ms	38820 KB

rle

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

vector <pii> X;
vector <int> V[4];
int D[101010], I[101010], P[2020202];
int n, m, s, mv;

int cost(int x, int t)
{
	if(t) return ((x - 1) / n + 1) * 3;
	else{
		int v = (x - 1 + n + 2) % (n + 2) + 1;
		return ((x - 1) / (n + 2)) * 3 + min(v, 3);
	}
}

void insert(int p)
{
	int d = D[p] % 4;
	I[p] = V[d].size();
	V[d].push_back(p);
}

void erase(int p)
{
	int d = D[p] % 4;
	swap(V[d][I[p]], V[d].back());
	swap(I[p], I[V[d][I[p]]]);
	V[d].pop_back();
}

void change(int &e, int x)
{
	printf("%d %d %d ", e, x, 0);
	e = x;
}

void make(int x, int y, int e)
{
	int t;
	
	if(x == e){
		for(; y; ){
			t = (y >= n? n - 1 : y - 1);
			printf("%d %d %d ", e, e, t);
			y -= t + 1;
		}
	}
	else{
		for(; y; ){
			t = (y >= n + 2? n - 1 : y - 3);
			if(t == -2) printf("%d ", x);
			else if(t == -1) printf("%d %d ", x, x);
			else if(t == 0) printf("%d %d %d ", x, x, x);
			else printf("%d %d %d ", e, x, t);
			y -= t + 3;
		}
	}
}

int main()
{
	int i, e, a, b, c, x, y, v;
	
	scanf("%d%d", &n, &m);
	
	for(i=0, e=0; i<m; i++){
		scanf("%d", &a);
		if(a == e){
			scanf("%d%d", &b, &c);
			if(b == e) x = e, y = c + 1;
			else if(c == 0) e = b, y = 0;
			else x = b, y = c + 3;
			i += 2;
		}
		else x = a, y = 1;
		
		if(!y) continue;
		if(!X.empty() && X.back().first == x) X.back().second += y;
		else X.emplace_back(x, y);
	}
	
	m = X.size();
	
	mv = 0;
	
	for(i=0; i<n; i++){
		insert(i);
	}
	
	for(i=m-1; i>=0; i--){
		tie(x, y) = X[i];
		v = cost(y, 0); c = cost(y, 1) - v; s += v;
		erase(x); for(; V[mv % 4].empty(); mv++);
		if(D[x] + c > mv + 3){
			P[i] = V[mv % 4].back() + 1;
			D[x] = mv + 3;
		}
		else D[x] += c;
		insert(x);
	}
	
	printf("%d\n", s + D[0]);
	
	for(i=0, e=0; i<m; i++){
		tie(x, y) = X[i];
		if(x == e && P[i]) change(e, P[i] - 1);
		make(x, y, e);
	}
	
	printf("\n");
	
	return 0;
}

Compilation message

rle.cpp: In function 'int main()':
rle.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
rle.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
rle.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &b, &c);
    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Incorrect	2 ms	376 KB	code is not the shortest
3	Correct	2 ms	376 KB	Output is correct
4	Incorrect	3 ms	376 KB	Unexpected end of file - int32 expected
5	Incorrect	2 ms	376 KB	code is not the shortest
6	Incorrect	20 ms	888 KB	Unexpected end of file - int32 expected
7	Incorrect	136 ms	3184 KB	Unexpected end of file - int32 expected
8	Incorrect	183 ms	4336 KB	Unexpected end of file - int32 expected
9	Incorrect	339 ms	11600 KB	Unexpected end of file - int32 expected
10	Incorrect	139 ms	2804 KB	Unexpected end of file - int32 expected
11	Incorrect	114 ms	3568 KB	code is not the shortest
12	Incorrect	230 ms	9308 KB	Unexpected end of file - int32 expected
13	Incorrect	291 ms	7916 KB	code is not the shortest
14	Correct	102 ms	4708 KB	Output is correct
15	Correct	54 ms	2792 KB	Output is correct
16	Correct	313 ms	10868 KB	Output is correct
17	Correct	347 ms	11876 KB	Output is correct
18	Incorrect	269 ms	8568 KB	the output code does not encode the input sequence
19	Correct	611 ms	31956 KB	Output is correct
20	Correct	628 ms	38820 KB	Output is correct