Submission #137706

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

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Incorrect	2 ms	376 KB	code is not the shortest
3	Incorrect	2 ms	376 KB	the output code does not encode the input sequence
4	Incorrect	3 ms	376 KB	the output code does not encode the input sequence
5	Incorrect	2 ms	376 KB	code is not the shortest
6	Incorrect	20 ms	832 KB	the output code does not encode the input sequence
7	Incorrect	135 ms	3172 KB	the output code does not encode the input sequence
8	Incorrect	181 ms	4504 KB	the output code does not encode the input sequence
9	Incorrect	342 ms	11600 KB	the output code does not encode the input sequence
10	Incorrect	139 ms	2676 KB	the output code does not encode the input sequence
11	Incorrect	113 ms	3696 KB	the output code does not encode the input sequence
12	Incorrect	228 ms	9308 KB	the output code does not encode the input sequence
13	Incorrect	288 ms	7928 KB	the output code does not encode the input sequence
14	Incorrect	102 ms	4704 KB	the output code does not encode the input sequence
15	Correct	53 ms	2768 KB	Output is correct
16	Correct	309 ms	10872 KB	Output is correct
17	Correct	344 ms	11876 KB	Output is correct
18	Incorrect	268 ms	8380 KB	the output code does not encode the input sequence
19	Correct	618 ms	32096 KB	Output is correct
20	Correct	632 ms	38876 KB	Output is correct