oj.uz

Submission #78917

# Submission time Handle Problem Language Result Execution time Memory
78917 2018-10-09T15:05:12 Z aminra Fibonacci representations (CEOI18_fib) C++14
20 / 100
 2040 ms 712 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)107;
const int infint = (int)1e9;
ll n, a[MAXN], dp1[MAXN], dp2[MAXN], fib[MAXN], dp[MAXN][MAXN], cp[MAXN], pc[MAXN];
vector<int> v;
ll get()
{
	dp1[0] = 1, dp2[0] = 0;
	for (int i = 1; i < v.size(); i++)
		dp1[i] = (dp1[i - 1] + dp2[i - 1]) % MOD, dp2[i] = dp1[i - 1] * ((v[i] - v[i - 1] - 1) / 2) % MOD + dp2[i - 1] * ((v[i] - v[i - 1]) / 2) % MOD, dp2[i] %= MOD;
	return (dp1[v.size() - 1] + dp2[v.size() - 1]) % MOD;
}
vector<ll> zeck(ll p)
{
	vector<ll> ans;
	for (int i = 25; i >= 1; i--)
		if(p >= fib[i])
		{
			p -= fib[i];
			ans.push_back(i);
		}
	return ans;
}
ll get(ll p)
{
	vector<ll> ans = zeck(p);
	reverse(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++)
		ans[i]--;
	memset(cp, 0, sizeof cp);
	memset(pc, 0, sizeof pc);
	cp[0] = dp[ans[0]][0];
	pc[0] = dp[ans[0]][0] - 1 + MOD, pc[0] %= MOD;
	for (int i = 1; i < ans.size(); i++)
	{
		cp[i] = cp[i - 1] * dp[ans[i]][ans[i - 1] + 1] % MOD;
		cp[i] += (dp[ans[i]][ans[i - 1]] - dp[ans[i]][ans[i - 1] + 1] + MOD) % MOD * pc[i - 1] % MOD, cp[i] %= MOD;
		pc[i] = cp[i - 1] * (dp[ans[i]][ans[i - 1] + 1] - 1) % MOD, pc[i] %= MOD;
		pc[i] += (dp[ans[i]][ans[i - 1]] - dp[ans[i]][ans[i - 1] + 1]) * pc[i - 1] % MOD;
	}
	return cp[ans.size() - 1];
}
void A()
{
	fib[1] = 1;
	fib[2] = 2;
	for (int i = 3; i <= 25; i++)
		fib[i] = fib[i - 1] + fib[i - 2];
	ll cur = 0;
	dp[0][0] = 1;
	for (int i = 1; i <= 25; i++)
		for (int j = 0; j <= i; j++)
		{
			dp[i][j] = 1;
			if(j <= i - 2)
				dp[i][j] += dp[i - 2][j], dp[i][j] %= MOD;
		}
	for (int i = 0; i < n; i++)
	{
		cur += fib[a[i]];
		cout << get(cur) << " ";
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	ll mx = 0;
	for (int i = 0; i < n; i++)
		mx = max(mx, a[i]);
	
	if(n <= 15 && mx <= 15)
	{
		A();
		return 0;
	}
	v.push_back(0);
	for (int i = 0; i < n; i++)
	{
		v.push_back(a[i]);
		sort(v.begin(), v.end());
		cout << get() << " ";
	}
}

Compilation message

fib.cpp: In function 'll get()':
fib.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++)
                  ~~^~~~~~~~~~
fib.cpp: In function 'll get(ll)':
fib.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++)
                  ~~^~~~~~~~~~~~
fib.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < ans.size(); i++)
                  ~~^~~~~~~~~~~~

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 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 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 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Incorrect 2 ms 508 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 556 KB Output is correct
2 Correct 2 ms 584 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Incorrect 2 ms 508 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2040 ms 712 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 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Incorrect 2 ms 508 KB Output isn't correct
8 Halted 0 ms 0 KB -