Submission #137737

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

void erase(ll p)
{
	ll d = D[p] % 10;
	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 % 10].empty(); mv++);
		if(D[x] + c > mv + 3){
			P[i] = V[mv % 10].back() + 1;
			D[x] = mv + 3;
		}
		else D[x] += c;
		_v = max(_v, D[x]);
		if(_v - mv > 3) return 1 / 0;
		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:107:28: warning: division by zero [-Wdiv-by-zero]
   if(_v - mv > 3) 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	47864 KB	Output is correct
2	Incorrect	45 ms	47736 KB	code is not the shortest
3	Correct	46 ms	47812 KB	Output is correct
4	Incorrect	46 ms	47992 KB	code is not the shortest
5	Incorrect	45 ms	47864 KB	code is not the shortest
6	Incorrect	67 ms	49264 KB	code is not the shortest
7	Incorrect	227 ms	58060 KB	code is not the shortest
8	Incorrect	290 ms	65232 KB	code is not the shortest
9	Incorrect	482 ms	82952 KB	code is not the shortest
10	Incorrect	227 ms	57988 KB	code is not the shortest
11	Incorrect	193 ms	57316 KB	code is not the shortest
12	Incorrect	342 ms	75836 KB	code is not the shortest
13	Incorrect	432 ms	71100 KB	code is not the shortest
14	Correct	175 ms	58844 KB	Output is correct
15	Correct	111 ms	53548 KB	Output is correct
16	Correct	460 ms	74248 KB	Output is correct
17	Correct	490 ms	77652 KB	Output is correct
18	Correct	509 ms	90076 KB	Output is correct
19	Correct	802 ms	132848 KB	Output is correct
20	Correct	831 ms	144992 KB	Output is correct