oj.uz

Submission #128513

# Submission time Handle Problem Language Result Execution time Memory
128513 2019-07-11T04:58:57 Z 윤교준(#3160) Fibonacci representations (CEOI18_fib) C++14
50 / 100
 4000 ms 1588 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<int> A;

int N;

bool has(int X) { return A.find(X) != A.end(); }
void insert(int X) { A.insert(X); }
void erase(int X) { A.erase(X); }

void push(int X) {
	if(X < 1) return;
	if(1 == X) X = 2;
	if(!has(X)) {
		insert(X);
		if(has(X-1)) {
			erase(X-1); erase(X);
			push(X+1);
			return;
		}
		for(int i = X; has(i) && has(i+1);) {
			erase(i); erase(i+1);
			i += 2;
			insert(i);
		}
		return;
	}
	int s = X, e = X;
	for(; 0 <= s-2 && has(s-2); s -= 2);
	for(; has(e+2); e += 2);
	for(int i = s; i <= e; i++) erase(i);
	for(int i = s+1; i < X; i += 2) insert(i);
	push(e+1);
	push(s-2);
}

ll getAns() {
	vector<pii> V;
	{
		int i = -1;
		for(int s : A) {
			if(s <= i) continue;
			i = s;
			int j = i; for(; has(j+2); j += 2);
			V.eb(i, j);
			i = j;
		}
	}

	//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);
		/*
		printf("PUSHED %d\n", x+1);
		for(int j = 0; j <= 50; j++) printf("%d", int(A[j]));
		puts("");
		*/
		cout << getAns() << endl;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 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 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 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 376 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 376 KB Output is correct
16 Correct 3 ms 256 KB Output is correct
17 Correct 3 ms 256 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 376 KB Output is correct
23 Correct 3 ms 256 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Execution timed out 4022 ms 1588 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 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 376 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 376 KB Output is correct
16 Correct 3 ms 256 KB Output is correct
17 Correct 3 ms 256 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 376 KB Output is correct
23 Correct 3 ms 256 KB Output is correct
24 Correct 3 ms 376 KB Output is correct
25 Execution timed out 4022 ms 1588 KB Time limit exceeded
26 Halted 0 ms 0 KB -