Submission #137712

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137712	2019-07-28T08:55:36 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	45 / 100	712 ms	65368 KB

rle

#include <bits/stdc++.h>

using namespace std;

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

vector <pll> X;
vector <ll> V[4];
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].push_back(p);
}

void erase(ll p)
{
	ll 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(ll &e, ll x)
{
	printf("%lld %lld 0 ", e, x);
	e = x;
}

void 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); 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 'int main()':
rle.cpp:67: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:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a);
   ~~~~~^~~~~~~~~~~~
rle.cpp:72: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

45.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Incorrect	2 ms	376 KB	code is not the shortest
3	Correct	2 ms	376 KB	Output is correct
4	Incorrect	3 ms	376 KB	Unexpected end of file - int32 expected
5	Incorrect	3 ms	376 KB	code is not the shortest
6	Incorrect	20 ms	1140 KB	Unexpected end of file - int32 expected
7	Incorrect	139 ms	3852 KB	Unexpected end of file - int32 expected
8	Incorrect	182 ms	4840 KB	Unexpected end of file - int32 expected
9	Incorrect	362 ms	19336 KB	Unexpected end of file - int32 expected
10	Incorrect	140 ms	3056 KB	Unexpected end of file - int32 expected
11	Incorrect	115 ms	4216 KB	code is not the shortest
12	Incorrect	244 ms	15056 KB	Unexpected end of file - int32 expected
13	Incorrect	291 ms	8932 KB	code is not the shortest
14	Correct	109 ms	7084 KB	Output is correct
15	Correct	57 ms	4040 KB	Output is correct
16	Correct	312 ms	11000 KB	Output is correct
17	Correct	350 ms	14428 KB	Output is correct
18	Correct	372 ms	19664 KB	Output is correct
19	Correct	677 ms	51480 KB	Output is correct
20	Correct	712 ms	65368 KB	Output is correct