oj.uz

답안 #128565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128565 2019-07-11T06:43:07 Z 윤교준(#3160) Fibonacci representations (CEOI18_fib) C++14
50 / 100
 4000 ms 1604 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MOD = 1000000007;

set<pii> CH;

set<pii>::iterator get(int X) { return prev(CH.upper_bound({X, INF})); }
bool has(int X) {
	auto it = CH.upper_bound({X, INF});
	if(CH.begin() == it) return false;
	int s, e; tie(s, e) = *prev(it);
	return s <= X && X <= e && (s&1) == (X&1);
}

void push(int X) {
	if(X < 1) return;
	if(1 == X) X = 2;
	if(!has(X)) {
		if(has(X-1) && !has(X+1)) {
			auto it = get(X-1);
			int s, e; tie(s, e) = *it;
			CH.erase(it); // TODO : erase
			e -= 2;
			if(s <= e) {
				CH.insert({s, e}); // TODO : insert
			}
			push(X+1);
			return;
		}
		if(!has(X-1) && has(X+1)) {
			auto it = get(X+1);
			int s, e; tie(s, e) = *it;
			CH.erase(it); // TODO : erase
			push(e+1);
			return;
		}
		if(has(X-1) && has(X+1)) {
			auto it = get(X);
			int s, e; tie(s, e) = *it;
			CH.erase(it); // TODO : erase
			CH.insert({s, X-1}); // TODO : insert
			push(e+1);
			return;
		}
		int s = X, e = X;
		if(has(X-2)) {
			auto it = get(X-2);
			int p, q; tie(p, q) = *it;
			CH.erase(it); // TODO : erase
			s = p;
		}
		if(has(X+2)) {
			auto it = get(X+2);
			int p, q; tie(p, q) = *it;
			CH.erase(it); // TODO : erase
			e = q;
		}
		CH.insert({s, e}); // TODO : insert
		return;
	}

	auto it = get(X);
	int s, e; tie(s, e) = *it;
	CH.erase(it); // TODO : erase
	if(s+1 < X) {
		CH.insert({s+1, X-1}); // TODO : insert
	}
	push(e+1);
	push(s-2);
}


int N;

ll getAns() {
	vector<pii> V;
	{
		for(auto &v : CH) V.eb(v);
	}

	//for(auto &v : V) printf("(%d,%d) ", v.first, v.second); puts("");

	vector<ll> DP[2];
	int N = sz(V);
	DP[0].resize(N); DP[1].resize(N);
	if(1 < V[0].first-2) {
		DP[0][0] = ll(V[0].first-4)/2 % MOD + 1;
	}
	DP[1][0] = 1 + ll(V[0].first-2)/2 * ((V[0].second-V[0].first)/2) % MOD;
	for(int i = 1; i < N; i++) {
		int l = V[i].first - V[i-1].second - 1;
		int c = (V[i].second - V[i].first)/2;
		DP[0][i] = (DP[1][i-1] * (l/2) % MOD) + (DP[0][i-1] * ((l+1)/2) % MOD);
		DP[0][i] %= MOD;
		DP[1][i] = DP[1][i-1] * (1 + (l/2) * c % MOD) % MOD;
		DP[1][i] += DP[0][i-1] * (1 + ((l+1)/2) * c % MOD) % MOD;
		DP[1][i] %= MOD;
	}
	//for(int i = 0; i < N; i++) printf("DP %d : %lld %lld\n", i, DP[0][i], DP[1][i]);
	return (DP[0].back() + DP[1].back()) % MOD;
}

int main() {
	cin >> N;
	for(int i = 0; i < N; i++) {
		int x;
		cin >> x;
		push(x+1);
		cout << getAns() << endl;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 252 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 256 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 252 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 3 ms 256 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 256 KB Output is correct
23 Correct 2 ms 256 KB Output is correct

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 256 KB Output is correct
2 Execution timed out 4013 ms 1604 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 252 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 3 ms 256 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 256 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 3 ms 256 KB Output is correct
25 Execution timed out 4013 ms 1604 KB Time limit exceeded
26 Halted 0 ms 0 KB -