oj.uz

답안 #137769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137769 2019-07-28T09:31:43 Z 김세빈(#3278) RLE (BOI06_rle) C++14
45 / 100
 808 ms 142660 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] % 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

# 결과 실행 시간 메모리 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