Submission #137742

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137742	2019-07-28T09:19:51 Z	김세빈(#3278)	RLE (BOI06_rle)	C++14	50 / 100	804 ms	144060 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] % 6;
	I[p] = V[d].size();
	V[d].pb(p);
}

void erase(ll p)
{
	ll d = D[p] % 6;
	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; ll _v = 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 % 6].empty(); mv++);
		if(D[x] + c > mv + 3){
			P[i] = V[mv % 6].back() + 1;
			D[x] = mv + 3;
		}
		else D[x] += c;
		_v = max(_v, D[x]);
		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: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

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	47864 KB	Output is correct
2	Incorrect	45 ms	47736 KB	code is not the shortest
3	Correct	46 ms	47864 KB	Output is correct
4	Correct	46 ms	47864 KB	Output is correct
5	Incorrect	46 ms	47864 KB	code is not the shortest
6	Incorrect	74 ms	49516 KB	code is not the shortest
7	Incorrect	227 ms	58072 KB	code is not the shortest
8	Incorrect	291 ms	65212 KB	code is not the shortest
9	Incorrect	494 ms	82748 KB	code is not the shortest
10	Incorrect	238 ms	58068 KB	code is not the shortest
11	Incorrect	190 ms	57600 KB	code is not the shortest
12	Incorrect	373 ms	75844 KB	code is not the shortest
13	Incorrect	434 ms	71172 KB	code is not the shortest
14	Correct	171 ms	58716 KB	Output is correct
15	Correct	110 ms	53476 KB	Output is correct
16	Correct	460 ms	74016 KB	Output is correct
17	Correct	512 ms	77792 KB	Output is correct
18	Correct	516 ms	90316 KB	Output is correct
19	Correct	787 ms	131352 KB	Output is correct
20	Correct	804 ms	144060 KB	Output is correct