Submission #137699

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137699	2019-07-28T08:41:57 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	15 / 100	628 ms	39112 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 >= 0) printf("%d %d %d ", e, x, t);
			else if(t == -2) printf("%d ", x);
			else if(t == -1) printf("%d %d ", x, x);
			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:68: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:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
rle.cpp:73: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

15.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	936 KB	Unexpected end of file - int32 expected
7	Incorrect	138 ms	3204 KB	Unexpected end of file - int32 expected
8	Incorrect	183 ms	4388 KB	Unexpected end of file - int32 expected
9	Incorrect	348 ms	11656 KB	Unexpected end of file - int32 expected
10	Incorrect	140 ms	2676 KB	Unexpected end of file - int32 expected
11	Incorrect	115 ms	3568 KB	the output code does not encode the input sequence
12	Incorrect	229 ms	9316 KB	Unexpected end of file - int32 expected
13	Incorrect	292 ms	7916 KB	the output code does not encode the input sequence
14	Incorrect	105 ms	4820 KB	the output code does not encode the input sequence
15	Incorrect	53 ms	2796 KB	the output code does not encode the input sequence
16	Incorrect	315 ms	11100 KB	the output code does not encode the input sequence
17	Incorrect	348 ms	11664 KB	the output code does not encode the input sequence
18	Incorrect	270 ms	8244 KB	the output code does not encode the input sequence
19	Correct	614 ms	31872 KB	Output is correct
20	Correct	628 ms	39112 KB	Output is correct