oj.uz

답안 #137716

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137716 2019-07-28T09:00:08 Z 김세빈(#3278) RLE (BOI06_rle) C++14
45 / 100
 760 ms 96408 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[4], 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;
	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;
}

void make(ll x, ll y, ll e)
{
	ll t;
	
	if(x == e){
		for(; y; ){
			t = (y >= n? n - 1 : y - 1);
			A.pb(e); A.pb(e); A.pb(t);
			y -= t + 1;
		}
	}
	else{
		for(; y; ){
			t = (y >= n + 2? n - 1 : y - 3);
			if(t == -2) A.pb(x);
			else if(t == -1) A.pb(x), A.pb(x);
			else if(t == 0) A.pb(x), A.pb(x), A.pb(x);
			else A.pb(e), A.pb(x), A.pb(t);
			y -= t + 3;
		}
	}
}

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); 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);
	}
	
	printf("%lld\n", s + D[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);
	}
	
	if(A.size() != s + D[0]) return 1 / 0;
	
	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:115:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(A.size() != s + D[0]) return 1 / 0;
     ~~~~~~~~~^~~~~~~~~~~
rle.cpp:115:36: warning: division by zero [-Wdiv-by-zero]
  if(A.size() != s + D[0]) return 1 / 0;
                                  ~~^~~
rle.cpp:117:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<A.size(); i++){
           ~^~~~~~~~~
rle.cpp:118:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   printf("%lld%c", A[i], " \n"[i == A.size() - 1]);
                                ~~^~~~~~~~~~~~~~~
rle.cpp:69: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:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a);
   ~~~~~^~~~~~~~~~~~
rle.cpp:74: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 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB code is not the shortest
3 Correct 2 ms 380 KB Output is correct
4 Runtime error 4 ms 632 KB Execution killed with signal 4 (could be triggered by violating memory limits)
5 Incorrect 2 ms 376 KB code is not the shortest
6 Runtime error 18 ms 3452 KB Execution killed with signal 4 (could be triggered by violating memory limits)
7 Runtime error 105 ms 16932 KB Execution killed with signal 4 (could be triggered by violating memory limits)
8 Runtime error 142 ms 21956 KB Execution killed with signal 4 (could be triggered by violating memory limits)
9 Runtime error 312 ms 58012 KB Execution killed with signal 4 (could be triggered by violating memory limits)
10 Runtime error 107 ms 17492 KB Execution killed with signal 4 (could be triggered by violating memory limits)
11 Incorrect 147 ms 9952 KB code is not the shortest
12 Runtime error 216 ms 41648 KB Execution killed with signal 4 (could be triggered by violating memory limits)
13 Incorrect 385 ms 23928 KB code is not the shortest
14 Correct 128 ms 11356 KB Output is correct
15 Correct 66 ms 6244 KB Output is correct
16 Correct 419 ms 26560 KB Output is correct
17 Correct 445 ms 33984 KB Output is correct
18 Correct 468 ms 42816 KB Output is correct
19 Correct 735 ms 83268 KB Output is correct
20 Correct 760 ms 96408 KB Output is correct