Submission #137659

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137659	2019-07-28T08:21:18 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	5 / 100	666 ms	67164 KB

rle

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

vector <pii> X;
vector <int> V[4];
int A[2020202];
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;
	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	252 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	19 ms	888 KB	Unexpected end of file - int32 expected
7	Incorrect	138 ms	3184 KB	Unexpected end of file - int32 expected
8	Incorrect	185 ms	4376 KB	Unexpected end of file - int32 expected
9	Runtime error	225 ms	16336 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Incorrect	139 ms	2768 KB	Unexpected end of file - int32 expected
11	Incorrect	115 ms	3412 KB	the output code does not encode the input sequence
12	Incorrect	242 ms	9580 KB	Output is corrupted
13	Incorrect	294 ms	7868 KB	the output code does not encode the input sequence
14	Incorrect	101 ms	4664 KB	the output code does not encode the input sequence
15	Incorrect	53 ms	2668 KB	the output code does not encode the input sequence
16	Incorrect	312 ms	10896 KB	the output code does not encode the input sequence
17	Incorrect	349 ms	12064 KB	the output code does not encode the input sequence
18	Runtime error	213 ms	7592 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	665 ms	64816 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	666 ms	67164 KB	Execution killed with signal 11 (could be triggered by violating memory limits)