Submission #137766

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

void erase(ll p)
{
	ll d = D[p] % 16, 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;
	
	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(V[mv % 16].empty() && D[x] != mv) return 1 / 0;
		for(; V[mv % 16].empty(); mv++);
		if(D[x] + c > mv + 3){
			P[i] = V[mv % 16].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:101:49: warning: division by zero [-Wdiv-by-zero]
   if(V[mv % 16].empty() && D[x] != mv) return 1 / 0;
                                               ~~^~~
rle.cpp:119:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<A.size(); i++){
           ~^~~~~~~~~
rle.cpp:120: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	Runtime error	107 ms	96376 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
3	Correct	46 ms	47864 KB	Output is correct
4	Incorrect	47 ms	47864 KB	code is not the shortest
5	Incorrect	47 ms	47864 KB	code is not the shortest
6	Runtime error	118 ms	97396 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
7	Incorrect	225 ms	58060 KB	code is not the shortest
8	Incorrect	297 ms	65240 KB	code is not the shortest
9	Runtime error	314 ms	117788 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
10	Incorrect	228 ms	58196 KB	code is not the shortest
11	Incorrect	191 ms	57440 KB	code is not the shortest
12	Incorrect	340 ms	75844 KB	code is not the shortest
13	Incorrect	441 ms	71100 KB	code is not the shortest
14	Correct	171 ms	58972 KB	Output is correct
15	Correct	110 ms	53476 KB	Output is correct
16	Correct	460 ms	74060 KB	Output is correct
17	Correct	506 ms	77652 KB	Output is correct
18	Correct	545 ms	90316 KB	Output is correct
19	Correct	783 ms	135192 KB	Output is correct
20	Correct	789 ms	144868 KB	Output is correct