Submission #137695

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137695	2019-07-28T08:38:18 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	15 / 100	629 ms	38896 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), 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:70: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:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
rle.cpp:75: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	956 KB	Unexpected end of file - int32 expected
7	Incorrect	137 ms	3312 KB	Unexpected end of file - int32 expected
8	Incorrect	184 ms	4376 KB	Unexpected end of file - int32 expected
9	Incorrect	345 ms	11444 KB	Unexpected end of file - int32 expected
10	Incorrect	140 ms	2676 KB	Unexpected end of file - int32 expected
11	Incorrect	115 ms	3516 KB	the output code does not encode the input sequence
12	Incorrect	229 ms	9184 KB	Unexpected end of file - int32 expected
13	Incorrect	291 ms	7960 KB	the output code does not encode the input sequence
14	Incorrect	101 ms	4580 KB	the output code does not encode the input sequence
15	Incorrect	54 ms	2708 KB	the output code does not encode the input sequence
16	Incorrect	316 ms	10860 KB	the output code does not encode the input sequence
17	Incorrect	347 ms	11624 KB	the output code does not encode the input sequence
18	Incorrect	267 ms	8156 KB	the output code does not encode the input sequence
19	Correct	619 ms	32076 KB	Output is correct
20	Correct	629 ms	38896 KB	Output is correct