Submission #898681

#TimeUsernameProblemLanguageResultExecution timeMemory
898681math_rabbit_1028Fibonacci representations (CEOI18_fib)C++14
50 / 100
4057 ms1512 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll MOD = 1e9 + 7; int n, arr[101010]; ll dp[101010]; vector<int> one(vector<int> vec) { vector<int> ret; while (true) { int f = 0; for (int i = 2; i < vec.size(); i++) { if (vec[i-1] + 1 == vec[i]) { f = i; break; } } if (f == 0) break; for (int i = 0; i < vec.size(); i++) { if (i == f || i == f-1) continue; ret.push_back(vec[i]); } ret.push_back(vec[f]+1); sort(ret.begin(), ret.end()); vec = ret; ret.clear(); } return vec; } vector<int> zero(vector<int> vec) { vector<int> ret; while (true) { int f = 0; for (int i = 2; i < vec.size(); i++) { if (vec[i-1] == vec[i]) { f = i; break; } } if (f == 0) break; for (int i = 0; i < vec.size(); i++) { if (i == f || i == f-1) continue; ret.push_back(vec[i]); } if (vec[f] == 1) ret.push_back(2); else if (vec[f] == 2) { ret.push_back(1); ret.push_back(3); } else { ret.push_back(vec[f]-2); ret.push_back(vec[f]+1); } sort(ret.begin(), ret.end()); vec = ret; ret.clear(); } return vec; } void solve(vector<int> vec) { sort(vec.begin(), vec.end()); vec = zero(vec); vec = one(vec); vec = zero(vec); vec = one(vec); int k = vec.size()-1; //for (int i = 1; i <= k; i++) cout << vec[i] << " "; cout << "\n"; for (int i = 0; i <= k; i++) dp[i] = 0; dp[0] = 1; dp[1] = (vec[1] + 1) / 2; for (int i = 2; i <= k; i++) { ll d = vec[i] - vec[i - 1]; if (d % 2 == 0) dp[i] = (dp[i-1] * ((d+3)/2) % MOD + MOD - dp[i-2]) % MOD; else dp[i] = dp[i-1] * ((d+1)/2) % MOD; } cout << dp[k] << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> arr[i]; vector<int> vec(1, 0); for (int i = 1; i <= n; i++) { vec.push_back(arr[i]); solve(vec); } return 0; }

Compilation message (stderr)

fib.cpp: In function 'std::vector<int> one(std::vector<int>)':
fib.cpp:13:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         for (int i = 2; i < vec.size(); i++) {
      |                         ~~^~~~~~~~~~~~
fib.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int i = 0; i < vec.size(); i++) {
      |                         ~~^~~~~~~~~~~~
fib.cpp: In function 'std::vector<int> zero(std::vector<int>)':
fib.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 2; i < vec.size(); i++) {
      |                         ~~^~~~~~~~~~~~
fib.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int i = 0; i < vec.size(); i++) {
      |                         ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...