oj.uz

Submission #70577

# Submission time Handle Problem Language Result Execution time Memory
70577 2018-08-23T06:28:31 Z 노영훈(#2185) Fibonacci representations (CEOI18_fib) C++11
25 / 100
 3 ms 824 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;

int n;


void solve0(){
	__int128 F[151], val=0;
	int one[151];
	int D[151], E[151]; // stay, down

	F[1]=1, F[2]=2;
	for(int i=3; i<=150; i++) F[i]=F[i-1]+F[i-2];



	for(int a; n--; ){
		cin>>a; assert(a<=100);
		val+=F[a];
		__int128 now=val;
		for(int i=1; i<=150; i++) one[i]=D[i]=E[i]=0;
		for(int i=150; i>=1; i--)
			if(F[i]<=now) now-=F[i], one[i]=1;
		// one is '11' free
		
//		for(int i=1; i<=10; i++) cout<<one[i];
//		cout<<'\n';

		D[0]=1, E[0]=0;
		ll ans=0;
		for(int i=1, j=0; i<=150; i++){
			if(!one[i]) continue;
			D[i] = (D[j] + E[j]) % MOD;
			E[i] = (ll(i-j-1)/2 * D[j] + ll(i-j)/2 * E[j]) % MOD;
			ans=(D[i]+E[i])%MOD;
			j=i;
		}
		cout<<ans<<'\n';
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	if(n<=100) solve0();
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 3 ms 620 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 3 ms 620 KB Output is correct
13 Runtime error 2 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 3 ms 620 KB Output is correct
13 Runtime error 2 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -