답안 #70577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70577	2018-08-23T06:28:31 Z	노영훈(#2185)	Fibonacci representations (CEOI18_fib)	C++11	25 / 100	3 ms	824 KB

fib

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	824 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 35.0

#	결과	실행 시간	메모리	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	-