Submission #137779

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137779	2019-07-28T09:37:23 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	55 / 100	749 ms	112680 KB

rle

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

vector <pll> X;
vector <ll> V[2020202], A;
ll D[101010], I[101010], P[2020202];
ll n, m, s, mv;

ll cost(ll x, ll t)
{
	if(t) return ((x - 1) / n + 1) * 3;
	else return x / (n + 2) * 3 + min(x % (n + 2), 3ll);
}

void insert(ll p)
{
	ll d = D[p] % 4;
	I[p] = V[d].size();
	V[d].pb(p);
}

void erase(ll p)
{
	ll d = D[p] % 4, q = V[d].back();
	swap(V[d][I[p]], V[d].back());
	swap(I[p], I[q]);
	V[d].pop_back();
}

void change(ll &e, ll x)
{
	printf("%lld %lld 0 ", e, x);
	e = x;
}

ll make(ll x, ll y, ll e)
{
	ll t;
	
	if(x == e){
		for(; y; ){
			t = (y >= n? n - 1 : y - 1);
			printf("%lld %lld %lld ", e, e, t);
			y -= t + 1;
		}
	}
	else{
		for(; y; ){
			t = (y >= n + 2? n - 1 : y - 3);
			if(t == -2) printf("%lld ", x);
			else if(t == -1) printf("%lld %lld ", x, x);
			else if(t == 0) printf("%lld %lld %lld ", x, x, x);
			else printf("%lld %lld %lld ", e, x, t);
			y -= t + 3;
		}
	}
}

int main()
{
	ll i, e, a, b, c, x, y, v;
	
	scanf("%lld%lld", &n, &m);
	
	for(i=0, e=0; i<m; i++){
		scanf("%lld", &a);
		if(a == e){
			scanf("%lld%lld", &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);
		
		if(c == 0) insert(x);
		else{	
			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("%lld\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 'll make(ll, ll, ll)':
rle.cpp:63:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
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("%lld%lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
rle.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a);
   ~~~~~^~~~~~~~~~~~
rle.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld", &b, &c);
    ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	47736 KB	Output is correct
2	Incorrect	45 ms	47736 KB	code is not the shortest
3	Correct	45 ms	47736 KB	Output is correct
4	Incorrect	46 ms	47992 KB	Unexpected end of file - int32 expected
5	Correct	46 ms	47864 KB	Output is correct
6	Incorrect	65 ms	48500 KB	Unexpected end of file - int32 expected
7	Incorrect	183 ms	51184 KB	Unexpected end of file - int32 expected
8	Incorrect	231 ms	52324 KB	code is not the shortest
9	Incorrect	405 ms	66720 KB	Unexpected end of file - int32 expected
10	Incorrect	187 ms	50544 KB	code is not the shortest
11	Correct	160 ms	51564 KB	Output is correct
12	Incorrect	321 ms	62620 KB	code is not the shortest
13	Incorrect	342 ms	56464 KB	code is not the shortest
14	Correct	152 ms	54620 KB	Output is correct
15	Correct	100 ms	51552 KB	Output is correct
16	Correct	359 ms	58616 KB	Output is correct
17	Correct	402 ms	61992 KB	Output is correct
18	Correct	423 ms	66984 KB	Output is correct
19	Correct	713 ms	99024 KB	Output is correct
20	Correct	749 ms	112680 KB	Output is correct