답안 #137786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137786 2019-07-28T09:40:48 Z 이온조(#3279) RLE (BOI06_rle) C++14
0 / 100
2500 ms 139300 KB
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pil = pair<int, long long>;
using tiii = tuple<int, int, int>;
#define X first
#define Y second
#define sz(V) ((int)V.size())

int N, M, K, A[2000009], mn[100009], mni[100009], fi[2000009], se[2000009], wh[4000009], ch[4000009];
int ofs, del[100009];
set<pii> col, st;
vector<pil> S;

void add(int a, int b) {
	if(S.empty()) S.push_back({a, b});
	else {
		if(S.back().X == a) S[sz(S) - 1].Y += b;
		else S.push_back({a, b});
	}
}

inline int get(int x) { return ofs + del[x]; }

vector<int> get4(int i) {
	int cnt = 4;
	vector<int> ret;
	for(auto& it: st) {
		ret.push_back(it.Y);
		if(--cnt == 0) break;
	}
	return ret;
}

pii getfi() { return (*col.begin()); }
pii getse() { return (*next(col.begin())); }

void upd(int i) {
	int el, me;
	int mod = S[i].Y % (N + 2);
	el = (S[i].Y) / (N + 2) * 3 + min(mod, 3);
	me = ((S[i].Y - 1) / N + 1) * 3;
	ofs += el;
	st.erase({del[S[i].X], S[i].X});
	del[S[i].X] += me - el;
	st.insert({del[S[i].X], S[i].X});
}

int f(int pos) { return pos <= K ? pos : pos - K; }

void go(int now) {
	if(now == 0) return;
	go(wh[now]);
	if(wh[now] != 0 || ch[now] != 0) printf("%d %d %d ", ch[wh[now]], ch[now], 0);
	for(int i=f(wh[now]) + 1; i<=f(now); i++) {
		while(S[i].Y > 0) {
			if(S[i].X == ch[now]) {
				printf("%d %d %d ", ch[now], ch[now], min(1LL*N, S[i].Y) - 1);
				S[i].Y -= min(1LL*N, S[i].Y);
			}
			else {
				printf("%d %d %d ", ch[now], S[i].X, min(1LL*N+2, S[i].Y) - 3);
				S[i].Y -= min(1LL*N+2, S[i].Y);
			}
		}
	}
}

int main() {
	scanf("%d%d",&N,&M);
	for(int i=1; i<=M; i++) scanf("%d", &A[i]);
	for(int i=1, r=0; i<=M; i++) {
		if(A[i] == r) {
			if(A[i+1] == r) add(r, A[i+2] + 1);
			else if(A[i+2] == 0) r = A[i+1];
			else add(A[i+1], A[i+2] + 3);
			i += 2;
		}
		else add(A[i], 1);
	}
	K = sz(S);
	S.insert(S.begin(), {0, 0});
	for(int i=0; i<N; i++) {
		st.insert({0, i});
		if(i <= 1) mn[i] = 0, mni[i] = 0;
		else mn[i] = 1e9, mni[i] = -1;
		col.insert({mn[i], i});
	}
	fi[0] = 0; se[0] = 0;
	for(int i=1; i<=K; i++) {
		upd(i);
		vector<int> T = get4(i); // 가장 작은 rm을 4개 꺼내온다.
		vector<tiii> R;
		for(auto& it: T) {
			if(it == getfi().Y) {
				int a, b; tie(a, b) = getse();
				R.push_back((tiii){b + get(it) + 3 + (i == 1 ? -3 : 0), it, mni[a]});
			}
			else {
				int a, b; tie(a, b) = getfi();
				R.push_back((tiii){b + get(it) + 3, it, mni[a]});
			}
		}
		sort(R.begin(), R.end());
		int fa, fb, fc, fv; tie(fa, fb, fc) = R[0]; fv = fa - get(fb);
		int sa, sb, sc, sv; tie(sa, sb, sc) = R[1]; sv = sa - get(sb);

		printf("fa: %d, fb: %d, fc: %d\n", fa, fb, fc);
		printf("sa: %d, sb: %d, sc: %d\n", sa, sb, sc);

		fi[i] = fa; wh[i] = fc; ch[i] = sb;
		if(mn[fb] > fv) {
			col.erase({mn[fb], fb});
			mn[fb] = fv, mni[fb] = i;
			col.insert({mn[fb], fb});
		}
		se[i] = sa; wh[i + K] = sc; ch[i + K] = fb;
		if(mn[sb] > sv) {
			col.erase({mn[sb], sb});
			mn[sb] = sv, mni[sb] = i + K;
			col.insert({mn[sb], sb});
		}

		printf("first: %d, second: %d\n", fi[i], se[i]);
	}
	printf("%d\n", fi[K]);
	go(K);
	return 0;
}

Compilation message

rle.cpp: In function 'void go(int)':
rle.cpp:58:65: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
     printf("%d %d %d ", ch[now], ch[now], min(1LL*N, S[i].Y) - 1);
                                           ~~~~~~~~~~~~~~~~~~~~~~^
rle.cpp:62:66: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
     printf("%d %d %d ", ch[now], S[i].X, min(1LL*N+2, S[i].Y) - 3);
                                          ~~~~~~~~~~~~~~~~~~~~~~~~^
rle.cpp: In function 'int main()':
rle.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~
rle.cpp:71:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=M; i++) scanf("%d", &A[i]);
                          ~~~~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Expected integer, but "fa:" found
2 Incorrect 2 ms 376 KB Expected integer, but "fa:" found
3 Incorrect 2 ms 376 KB Expected integer, but "fa:" found
4 Incorrect 3 ms 376 KB Expected integer, but "fa:" found
5 Incorrect 4 ms 504 KB Expected integer, but "fa:" found
6 Incorrect 40 ms 3060 KB Expected integer, but "fa:" found
7 Incorrect 208 ms 11776 KB Expected integer, but "fa:" found
8 Incorrect 256 ms 13656 KB Expected integer, but "fa:" found
9 Incorrect 1138 ms 92556 KB Expected integer, but "fa:" found
10 Incorrect 189 ms 9636 KB Expected integer, but "fa:" found
11 Incorrect 193 ms 11500 KB Expected integer, but "fa:" found
12 Incorrect 871 ms 67752 KB Expected integer, but "fa:" found
13 Incorrect 456 ms 25572 KB Expected integer, but "fa:" found
14 Incorrect 426 ms 29760 KB Expected integer, but "fa:" found
15 Incorrect 223 ms 15204 KB Expected integer, but "fa:" found
16 Incorrect 342 ms 17348 KB Expected integer, but "fa:" found
17 Incorrect 723 ms 43844 KB Expected integer, but "fa:" found
18 Incorrect 1027 ms 55504 KB Expected integer, but "fa:" found
19 Execution timed out 2606 ms 139300 KB Time limit exceeded
20 Execution timed out 2542 ms 136964 KB Time limit exceeded