Submission #137729

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137729	2019-07-28T09:14:04 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	45 / 100	787 ms	144892 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];
	I[p] = V[d].size();
	V[d].pb(p);
}

void erase(ll p)
{
	ll d = D[p];
	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)
{
	A.pb(e); A.pb(x); A.pb(0);
	e = x;
}

ll make(ll x, ll y, ll e)
{
	ll t, ret = 0;
	
	if(x == e){
		for(; y; ){
			t = (y >= n? n - 1 : y - 1);
			A.pb(e); A.pb(e); A.pb(t); ret += 3;
			y -= t + 1;
		}
	}
	else{
		for(; y; ){
			t = (y >= n + 2? n - 1 : y - 3);
			if(t == -2) A.pb(x), ret += 1;
			else if(t == -1) A.pb(x), A.pb(x), ret += 2;
			else if(t == 0) A.pb(x), A.pb(x), A.pb(x), ret += 3;
			else A.pb(e), A.pb(x), A.pb(t), ret += 3;
			y -= t + 3;
		}
	}
	
	return ret;
}

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].empty(); mv++);
		if(D[x] + c > mv + 3){
			if(V[mv].back() == x) return 1 / 0;
			P[i] = V[mv].back() + 1;
			D[x] = mv + 3;
		}
		else D[x] += c;
		insert(x);
	}
	
	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("%lld\n", (ll)A.size());
	
	for(i=0; i<A.size(); i++){
		printf("%lld%c", A[i], " \n"[i == A.size() - 1]);
	}
	
	return 0;
}

Compilation message

rle.cpp: In function 'int main()':
rle.cpp:102:35: warning: division by zero [-Wdiv-by-zero]
    if(V[mv].back() == x) return 1 / 0;
                                 ~~^~~
rle.cpp:118:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<A.size(); i++){
           ~^~~~~~~~~
rle.cpp:119:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   printf("%lld%c", A[i], " \n"[i == A.size() - 1]);
                                ~~^~~~~~~~~~~~~~~
rle.cpp:71: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:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a);
   ~~~~~^~~~~~~~~~~~
rle.cpp:76: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	48 ms	47864 KB	Output is correct
2	Incorrect	51 ms	47736 KB	code is not the shortest
3	Correct	46 ms	47884 KB	Output is correct
4	Incorrect	47 ms	47996 KB	code is not the shortest
5	Incorrect	46 ms	47864 KB	code is not the shortest
6	Incorrect	75 ms	49520 KB	code is not the shortest
7	Incorrect	226 ms	58420 KB	code is not the shortest
8	Incorrect	291 ms	65500 KB	code is not the shortest
9	Incorrect	516 ms	92508 KB	code is not the shortest
10	Incorrect	232 ms	58196 KB	code is not the shortest
11	Incorrect	190 ms	57316 KB	code is not the shortest
12	Incorrect	339 ms	77504 KB	code is not the shortest
13	Incorrect	436 ms	71488 KB	code is not the shortest
14	Correct	171 ms	59100 KB	Output is correct
15	Correct	109 ms	53476 KB	Output is correct
16	Correct	463 ms	74364 KB	Output is correct
17	Correct	494 ms	77892 KB	Output is correct
18	Correct	532 ms	90180 KB	Output is correct
19	Correct	787 ms	143892 KB	Output is correct
20	Correct	779 ms	144892 KB	Output is correct