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
#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);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
# 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