oj.uz

Submission #128512

# Submission time Handle Problem Language Result Execution time Memory
128512 2019-07-11T04:56:23 Z 윤교준(#3160) Fibonacci representations (CEOI18_fib) C++14
25 / 100
 4 ms 380 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;

bitset<5555> A;

int N;

void push(int X) {
	if(X < 1) return;
	if(1 == X) X = 2;
	if(!A[X]) {
		A[X] = true;
		if(A[X-1]) {
			A[X-1] = A[X] = false;
			push(X+1);
			return;
		}
		for(int i = X; A[i] && A[i+1];) {
			A[i] = A[i+1] = false;
			i += 2;
			A[i] = true;
		}
		return;
	}
	int s = X, e = X;
	for(; 0 <= s-2 && A[s-2]; s -= 2);
	for(; A[e+2]; e += 2);
	for(int i = s; i <= e; i++) A[i] = false;
	for(int i = s+1; i < X; i += 2) A[i] = true;
	push(e+1);
	push(s-2);
}

ll getAns() {
	vector<pii> V;
	for(int i = 1; i < 5000; i++) if(A[i]) {
		int j = i; for(; A[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 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)