Submission #826298

#TimeUsernameProblemLanguageResultExecution timeMemory
826298TsovakFibonacci representations (CEOI18_fib)C++17
50 / 100
4014 ms3152 KiB
// -------------------- Includes -------------------- // #define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include <iostream> #include <iomanip> #include <cstdio> #include <stdio.h> #include <cstdlib> #include <stdlib.h> #include <array> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <math.h> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <vector> #include <stack> #include <queue> #include <deque> #include <bitset> #include <list> #include <iterator> #include <numeric> #include <complex> #include <tuple> #include <utility> #include <cassert> #include <assert.h> #include <climits> #include <limits.h> #include <ctime> #include <time.h> #include <random> #include <chrono> #include <fstream> using namespace std; // -------------------- Typedefs -------------------- // typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ld; // -------------------- Defines -------------------- // #define pr pair #define mpr make_pair #define ff first #define ss second #define mset multiset #define mmap multimap #define uset unordered_set #define umap unordered_map #define umset unordered_multiset #define ummap unordered_multimap #define pqueue priority_queue #define sz(x) (int((x).size())) #define len(x) (int((x).length())) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define clr(x) (x).clear() #define pf push_front #define pb push_back #define popf pop_front #define popb pop_back #define ft front #define bk back #define lb lower_bound #define ub upper_bound #define bs binary_search // -------------------- Constants -------------------- // const int MAX = int(1e9 + 5); const ll MAXL = ll(1e18 + 5); const ll MOD = ll(1e9 + 7); const ll MOD2 = ll(998244353); // -------------------- Functions -------------------- // void fastio() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); return; } void precision(int x) { cout.setf(ios::fixed | ios::showpoint); cout.precision(x); return; } ll gcd(ll a, ll b) { while (b) { a %= b; swap(a, b); } return a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } bool is_prime(ll a) { if (a == 1) { return false; } for (ll i = 2; i * i <= a; i++) { if (a % i == 0) { return false; } } return true; } bool is_square(ll a) { ll b = ll(sqrt(a)); return (b * b == a); } bool is_cube(ll a) { ll b = ll(cbrt(a)); return (b * b * b == a); } int digit_sum(ll a) { int sum = 0; while (a) { sum += int(a % 10); a /= 10; } return sum; } ll binpow(ll a, int b) { ll ans = 1; while (b) { if ((b & 1) == 1) { ans *= a; } b >>= 1; a *= a; } return ans; } ll binpow_by_mod(ll a, ll b, ll mod) { ll ans = 1; while (b) { if ((b & 1) == 1) { ans *= a; ans %= mod; } b >>= 1; a *= a; a %= mod; } return ans; } ll factorial(int a) { ll ans = 1; for (int i = 2; i <= a; i++) { ans *= ll(i); } return ans; } ll factorial_by_mod(int a, ll mod) { ll ans = 1; for (int i = 2; i <= a; i++) { ans *= ll(i); ans %= mod; } return ans; } // -------------------- Solution -------------------- // const int N = 100005; int a[N]; int n; set<int> st; vector<int> v; void add(int x) { if (st.empty()) { st.insert(x); return; } int i, j; auto it = st.lb(x); if (it == st.end()) { it--; if (*it == x - 1) { st.erase(it); st.insert(x + 1); } else st.insert(x); return; } if (*it == x + 1) { st.erase(it); add(x + 2); return; } if (it != st.begin()) { it--; if (*it == x - 1) { st.erase(it); add(x + 1); return; } it++; } if (*it >= x + 2) { st.insert(x); return; } st.erase(it); if (x == 1) add(2); else if (x == 2) { add(1); add(3); } else { add(x - 2); add(x + 1); } return; } ll dp[N][2]; void solve() { int i, j; cin >> n; for (i = 1; i <= n; i++) { cin >> a[i]; } for (i = 1; i <= n; i++) { add(a[i]); clr(v); for (auto j : st) v.pb(j); dp[0][0] = 1; dp[0][1] = ((v[0] + 1) / 2 - 1) % MOD; for (j = 1; j < sz(v); j++) { dp[j][0] = (dp[j - 1][0] + dp[j - 1][1]) % MOD; dp[j][1] = (((v[j] - v[j - 1] - 1) / 2) * dp[j - 1][0]) % MOD; dp[j][1] += (((v[j] - v[j - 1]) / 2) * dp[j - 1][1]) % MOD; dp[j][1] %= MOD; } cout << (dp[sz(v) - 1][0] + dp[sz(v) - 1][1]) % MOD << "\n"; } return; } void precalc() { return; } int main() { fastio(); precalc(); int tests = 1, tc; //cin >> tests; for (tc = 1; tc <= tests; tc++) { solve(); } //cout << db(clock()) / CLOCKS_PER_SEC << endl; return 0; } /* # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # */

Compilation message (stderr)

fib.cpp: In function 'void add(int)':
fib.cpp:217:6: warning: unused variable 'i' [-Wunused-variable]
  217 |  int i, j;
      |      ^
fib.cpp:217:9: warning: unused variable 'j' [-Wunused-variable]
  217 |  int i, j;
      |         ^
#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...