답안 #137707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137707	2019-07-28T08:50:36 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	40 / 100	650 ms	38892 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 / (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

40.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Incorrect	2 ms	376 KB	code is not the shortest
3	Correct	2 ms	380 KB	Output is correct
4	Incorrect	3 ms	376 KB	Unexpected end of file - int32 expected
5	Incorrect	2 ms	376 KB	code is not the shortest
6	Incorrect	20 ms	892 KB	Unexpected end of file - int32 expected
7	Incorrect	136 ms	3180 KB	Unexpected end of file - int32 expected
8	Incorrect	183 ms	4356 KB	Unexpected end of file - int32 expected
9	Incorrect	340 ms	11472 KB	Unexpected end of file - int32 expected
10	Incorrect	141 ms	2804 KB	Unexpected end of file - int32 expected
11	Incorrect	113 ms	3572 KB	code is not the shortest
12	Incorrect	232 ms	9472 KB	Unexpected end of file - int32 expected
13	Incorrect	291 ms	8020 KB	code is not the shortest
14	Correct	102 ms	4708 KB	Output is correct
15	Correct	54 ms	2796 KB	Output is correct
16	Correct	327 ms	10860 KB	Output is correct
17	Correct	349 ms	11964 KB	Output is correct
18	Incorrect	270 ms	8396 KB	the output code does not encode the input sequence
19	Correct	650 ms	31816 KB	Output is correct
20	Correct	622 ms	38892 KB	Output is correct