Submission #137769

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

void erase(ll p)
{
	ll d = D[p] % 4, 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 % 4].empty() && D[x] != mv) return 1 / 0;
		for(; V[mv % 4].empty(); mv++);
		if(D[x] + c > mv + 3){
			P[i] = V[mv % 4].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:48: warning: division by zero [-Wdiv-by-zero]
   if(V[mv % 4].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	47740 KB	Output is correct
2	Runtime error	108 ms	96632 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
3	Correct	46 ms	47736 KB	Output is correct
4	Runtime error	108 ms	96596 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
5	Incorrect	46 ms	47992 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	Runtime error	197 ms	98372 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
8	Runtime error	206 ms	98152 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
9	Runtime error	312 ms	117820 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
10	Runtime error	183 ms	97776 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
11	Incorrect	190 ms	57272 KB	code is not the shortest
12	Runtime error	240 ms	112656 KB	Execution killed with signal 4 (could be triggered by violating memory limits)
13	Incorrect	432 ms	71184 KB	code is not the shortest
14	Correct	177 ms	58716 KB	Output is correct
15	Correct	109 ms	53476 KB	Output is correct
16	Correct	482 ms	74168 KB	Output is correct
17	Correct	510 ms	81452 KB	Output is correct
18	Correct	522 ms	90276 KB	Output is correct
19	Correct	774 ms	129960 KB	Output is correct
20	Correct	808 ms	142660 KB	Output is correct