Submission #137690

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137690	2019-07-28T08:34:26 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	5 / 100	2500 ms	36368 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[101010];
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;
	if(V[d].size() <= I[p]) for(; ; );
	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 >= 0){
				printf("%d %d %d ", e, x, t);
			}
			else if(t == -2) printf("%d ", x), y = 0;
			else if(t == -1) printf("%d %d ", x, x), y = 0;
			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(e == x && P[i]) change(e, P[i] - 1);
		make(x, y, e);
	}
	
	printf("\n");
	
	return 0;
}

Compilation message

rle.cpp: In function 'void erase(int)':
rle.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(V[d].size() <= I[p]) for(; ; );
     ~~~~~~~~~~~~^~~~~~~
rle.cpp: In function 'int main()':
rle.cpp:71: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:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
rle.cpp:76: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

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Incorrect	2 ms	376 KB	the output code does not encode the input sequence
3	Incorrect	2 ms	376 KB	the output code does not encode the input sequence
4	Incorrect	3 ms	376 KB	Unexpected end of file - int32 expected
5	Incorrect	2 ms	376 KB	the output code does not encode the input sequence
6	Incorrect	20 ms	888 KB	Unexpected end of file - int32 expected
7	Incorrect	138 ms	3128 KB	Unexpected end of file - int32 expected
8	Incorrect	182 ms	4336 KB	Unexpected end of file - int32 expected
9	Runtime error	206 ms	11344 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Incorrect	140 ms	2672 KB	Unexpected end of file - int32 expected
11	Incorrect	113 ms	3568 KB	the output code does not encode the input sequence
12	Runtime error	127 ms	8492 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Incorrect	289 ms	7832 KB	the output code does not encode the input sequence
14	Execution timed out	2515 ms	2540 KB	Time limit exceeded
15	Incorrect	53 ms	2796 KB	the output code does not encode the input sequence
16	Incorrect	311 ms	10900 KB	the output code does not encode the input sequence
17	Execution timed out	2532 ms	2680 KB	Time limit exceeded
18	Execution timed out	2519 ms	4504 KB	Time limit exceeded
19	Runtime error	332 ms	36368 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	330 ms	35316 KB	Execution killed with signal 11 (could be triggered by violating memory limits)