Submission #137776

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137776	2019-07-28T09:35:16 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	0 / 100	745 ms	112792 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)
{
	A.pb(e); A.pb(x); A.pb(0);
	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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	46 ms	47736 KB	Unexpected end of file - int32 expected
2	Incorrect	45 ms	47864 KB	code is not the shortest
3	Incorrect	46 ms	47864 KB	Unexpected end of file - int32 expected
4	Incorrect	47 ms	47864 KB	Unexpected end of file - int32 expected
5	Incorrect	53 ms	47864 KB	Unexpected end of file - int32 expected
6	Incorrect	65 ms	48548 KB	Unexpected end of file - int32 expected
7	Incorrect	182 ms	51180 KB	Unexpected end of file - int32 expected
8	Incorrect	240 ms	52328 KB	Unexpected end of file - int32 expected
9	Incorrect	403 ms	67004 KB	Unexpected end of file - int32 expected
10	Incorrect	200 ms	50416 KB	Unexpected end of file - int32 expected
11	Incorrect	166 ms	51692 KB	Unexpected end of file - int32 expected
12	Incorrect	290 ms	62544 KB	Unexpected end of file - int32 expected
13	Incorrect	346 ms	56412 KB	Unexpected end of file - int32 expected
14	Incorrect	153 ms	54584 KB	Unexpected end of file - int32 expected
15	Incorrect	100 ms	51556 KB	Unexpected end of file - int32 expected
16	Incorrect	356 ms	58488 KB	Unexpected end of file - int32 expected
17	Incorrect	397 ms	61972 KB	Unexpected end of file - int32 expected
18	Incorrect	431 ms	67184 KB	Unexpected end of file - int32 expected
19	Incorrect	743 ms	98968 KB	Unexpected end of file - int32 expected
20	Incorrect	745 ms	112792 KB	Unexpected end of file - int32 expected