Submission #137685

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137685	2019-07-28T08:33:23 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	5 / 100	2500 ms	36472 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].empty()) 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 '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	3 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	137 ms	3180 KB	Unexpected end of file - int32 expected
8	Incorrect	182 ms	4332 KB	Unexpected end of file - int32 expected
9	Runtime error	199 ms	11112 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Incorrect	142 ms	2700 KB	Unexpected end of file - int32 expected
11	Incorrect	113 ms	3592 KB	the output code does not encode the input sequence
12	Runtime error	127 ms	8416 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Incorrect	291 ms	7964 KB	the output code does not encode the input sequence
14	Incorrect	103 ms	4580 KB	the output code does not encode the input sequence
15	Incorrect	54 ms	2684 KB	the output code does not encode the input sequence
16	Incorrect	317 ms	10864 KB	the output code does not encode the input sequence
17	Incorrect	343 ms	11364 KB	the output code does not encode the input sequence
18	Execution timed out	2597 ms	4580 KB	Time limit exceeded
19	Runtime error	331 ms	36472 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	327 ms	35304 KB	Execution killed with signal 11 (could be triggered by violating memory limits)