Submission #137934

# Submission time Handle Problem Language Result Execution time Memory
137934 2019-07-28T14:32:56 Z sebinkim RLE (BOI06_rle) C++14
55 / 100
748 ms 112860 KB
#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;
		if(c == 0) continue;
		
		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 '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);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 46 ms 47736 KB Output is correct
2 Incorrect 46 ms 47736 KB code is not the shortest
3 Correct 52 ms 47832 KB Output is correct
4 Incorrect 48 ms 47864 KB Unexpected end of file - int32 expected
5 Correct 58 ms 47736 KB Output is correct
6 Incorrect 65 ms 48500 KB Unexpected end of file - int32 expected
7 Incorrect 183 ms 51180 KB Unexpected end of file - int32 expected
8 Incorrect 231 ms 52420 KB code is not the shortest
9 Incorrect 409 ms 66676 KB Unexpected end of file - int32 expected
10 Incorrect 187 ms 50544 KB code is not the shortest
11 Correct 160 ms 51692 KB Output is correct
12 Incorrect 287 ms 62392 KB code is not the shortest
13 Incorrect 343 ms 56548 KB code is not the shortest
14 Correct 153 ms 54748 KB Output is correct
15 Correct 101 ms 51520 KB Output is correct
16 Correct 355 ms 58488 KB Output is correct
17 Correct 396 ms 61972 KB Output is correct
18 Correct 419 ms 66512 KB Output is correct
19 Correct 723 ms 98896 KB Output is correct
20 Correct 748 ms 112860 KB Output is correct