Submission #137756

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

void erase(ll p)
{
	ll d = D[p] % 9, 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, 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);
		int _s=0;for(int j=0; j<9; j++) _s += V[j].size();
		if(_s != n - 1) return 1 / 0;
		for(; V[mv % 9].empty(); mv++);
		if(D[x] + c > mv + 3){
			P[i] = V[mv % 9].back() + 1;
			D[x] = mv + 3;
		}
		else D[x] += c;
		_v = max(_v, D[x]);
		insert(x);
		_s=0; for(int j=0; j<9; j++) _s += V[j].size();
		if(_s != n) return 1 / 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("%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:28: warning: division by zero [-Wdiv-by-zero]
   if(_s != n - 1) return 1 / 0;
                          ~~^~~
rle.cpp:112:24: warning: division by zero [-Wdiv-by-zero]
   if(_s != n) return 1 / 0;
                      ~~^~~
rle.cpp:123:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<A.size(); i++){
           ~^~~~~~~~~
rle.cpp:124: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	45 ms	47736 KB	Output is correct
2	Incorrect	46 ms	47736 KB	code is not the shortest
3	Correct	46 ms	47864 KB	Output is correct
4	Incorrect	47 ms	47992 KB	code is not the shortest
5	Incorrect	46 ms	47864 KB	code is not the shortest
6	Incorrect	69 ms	49392 KB	code is not the shortest
7	Incorrect	234 ms	58072 KB	code is not the shortest
8	Incorrect	297 ms	65304 KB	code is not the shortest
9	Incorrect	490 ms	82708 KB	code is not the shortest
10	Incorrect	228 ms	58032 KB	code is not the shortest
11	Incorrect	193 ms	57384 KB	code is not the shortest
12	Incorrect	342 ms	75780 KB	code is not the shortest
13	Incorrect	434 ms	71140 KB	code is not the shortest
14	Correct	174 ms	58868 KB	Output is correct
15	Correct	110 ms	53476 KB	Output is correct
16	Correct	470 ms	74084 KB	Output is correct
17	Correct	493 ms	77664 KB	Output is correct
18	Correct	518 ms	90084 KB	Output is correct
19	Correct	833 ms	133340 KB	Output is correct
20	Correct	850 ms	144812 KB	Output is correct