Submission #137907

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137907	2019-07-28T13:46:38 Z	sebinkim	RLE (BOI06_rle)	C++14	55 / 100	733 ms	112744 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	45 ms	47736 KB	Output is correct
2	Incorrect	46 ms	47736 KB	code is not the shortest
3	Correct	51 ms	47764 KB	Output is correct
4	Incorrect	47 ms	47864 KB	Unexpected end of file - int32 expected
5	Correct	46 ms	47824 KB	Output is correct
6	Incorrect	64 ms	48496 KB	Unexpected end of file - int32 expected
7	Incorrect	185 ms	51296 KB	Unexpected end of file - int32 expected
8	Incorrect	230 ms	52200 KB	code is not the shortest
9	Incorrect	414 ms	66792 KB	Unexpected end of file - int32 expected
10	Incorrect	187 ms	50544 KB	code is not the shortest
11	Correct	161 ms	51560 KB	Output is correct
12	Incorrect	301 ms	62544 KB	code is not the shortest
13	Incorrect	342 ms	56456 KB	code is not the shortest
14	Correct	152 ms	54620 KB	Output is correct
15	Correct	100 ms	51556 KB	Output is correct
16	Correct	358 ms	58508 KB	Output is correct
17	Correct	400 ms	61924 KB	Output is correct
18	Correct	429 ms	67064 KB	Output is correct
19	Correct	718 ms	98968 KB	Output is correct
20	Correct	733 ms	112744 KB	Output is correct