답안 #137725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137725	2019-07-28T09:11:18 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	45 / 100	782 ms	144888 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){
			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);
	}
	
//	if(A.size() != s + D[0]) return 1 / 0;
	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: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

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	47736 KB	Output is correct
2	Incorrect	58 ms	47940 KB	code is not the shortest
3	Correct	55 ms	47816 KB	Output is correct
4	Incorrect	57 ms	47864 KB	code is not the shortest
5	Incorrect	56 ms	47864 KB	code is not the shortest
6	Incorrect	75 ms	49544 KB	code is not the shortest
7	Incorrect	231 ms	58460 KB	code is not the shortest
8	Incorrect	292 ms	65628 KB	code is not the shortest
9	Incorrect	499 ms	92604 KB	code is not the shortest
10	Incorrect	235 ms	58320 KB	code is not the shortest
11	Incorrect	201 ms	57440 KB	code is not the shortest
12	Incorrect	352 ms	77604 KB	code is not the shortest
13	Incorrect	435 ms	71484 KB	code is not the shortest
14	Correct	171 ms	59072 KB	Output is correct
15	Correct	109 ms	53536 KB	Output is correct
16	Correct	463 ms	74152 KB	Output is correct
17	Correct	494 ms	77832 KB	Output is correct
18	Correct	516 ms	90196 KB	Output is correct
19	Correct	778 ms	143832 KB	Output is correct
20	Correct	782 ms	144888 KB	Output is correct