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
#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);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
# 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