oj.uz

Submission #73467

# Submission time Handle Problem Language Result Execution time Memory
73467 2018-08-28T09:55:15 Z duckmoon99 Fibonacci representations (CEOI18_fib) C++14
5 / 100
 4000 ms 544 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e18
#define ret return

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const ll MOD = 1e9+7;

struct mat{
	ll a[2][2];
	void ini(ll a1, ll a2, ll a3, ll a4){
		a[0][0]=a1;
		a[0][1]=a2;
		a[1][0]=a3;
		a[1][1]=a4;
	}
};

ll add(ll a, ll b){
	ll res=(a+MOD)+(b+MOD);
	res%=MOD;
	ret res;
}

ll mult(ll a, ll b){
	ll res = (a+MOD)*b+(MOD);
	res%=MOD;
	ret res;
}

mat mat_mult(mat A, mat B){
	mat res;
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 2; j++){
			res.a[0][0]=add(mult(A.a[0][0],B.a[0][0]),mult(A.a[0][1],B.a[1][0]));
			res.a[0][1]=add(mult(A.a[0][0],B.a[0][1]),mult(A.a[0][1],B.a[1][1]));
			res.a[1][0]=add(mult(A.a[1][0],B.a[0][0]),mult(A.a[1][1],B.a[1][0]));
			res.a[1][1]=add(mult(A.a[1][0],B.a[0][1]),mult(A.a[1][1],B.a[1][1]));
		}
	}
	ret res;
}

ll a[111];

mat mat_exp(mat a, int n){
	if(n==1)ret a;
	if(n%2){
		mat res = mat_exp(a,n-1);
		ret mat_mult(res,a);
	}
	else{
		mat res = mat_exp(a,n/2);
		ret mat_mult(res,res);
	}
}

mat cur, r;

ll solve(ll p, int q){
	if(p==0){
		ret 1;
	}
	if(q==0){
		ret 0;
	}
	ll res = 0;
	for(int i = q; i >= 1; i--){
		if(mat_exp(r,i).a[0][0]<=p){
			res=add(res,solve(p-mat_exp(r,i).a[0][0],i-1));
		}
	}
	ret res;
}

int main(){
	int n;
	cin >> n;
	ll p=0;
	cur.ini(1,1,1,0);
	r=cur;
	int q = 1;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		p+=mat_exp(r,a[i]).a[0][0];
		while(mat_mult(cur,r).a[0][0]<=p){
			cur=mat_mult(cur,r);
			q++;
		}
		cout << solve(p,q) << endl;
	}

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 36 ms 376 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 338 ms 544 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 36 ms 376 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 338 ms 544 KB Output is correct
7 Correct 19 ms 544 KB Output is correct
8 Execution timed out 4019 ms 544 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4014 ms 544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 36 ms 376 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 338 ms 544 KB Output is correct
7 Correct 19 ms 544 KB Output is correct
8 Execution timed out 4019 ms 544 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4094 ms 544 KB Time limit exceeded
2 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 36 ms 376 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 338 ms 544 KB Output is correct
7 Correct 19 ms 544 KB Output is correct
8 Execution timed out 4019 ms 544 KB Time limit exceeded
9 Halted 0 ms 0 KB -