Submission #161421

#	Time	Username	Problem	Language	Result	Execution time	Memory
161421		rama_pang	Fibonacci representations (CEOI18_fib)	C++14	50 / 100	4022 ms	2640 KiB

fib

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MOD = 1e9 + 7;

map<int, int> canonical; 

void balance(int n) {
    if (canonical[n] == 0) return;

    bool changed = false;

    if (canonical[n] == 2) {
        changed = true;
        canonical[n] = 0;
        canonical[n + 1]++;
        if (n == 1) 
            canonical[n - 1]++; // since F(0) = F(1) = 1
        else if (n >= 2) 
            canonical[n - 2]++; // otherwise
    }

    if (n >= 1 && canonical[n] && canonical[n - 1]) { // can be reduced to F(n + 1)
        changed = true;
        canonical[n]--;
        canonical[n - 1]--;
        canonical[n + 1]++;
    }

    if (canonical[n + 1] && canonical[n]) { // can be reduced to F(n + 2)
        changed = true;
        canonical[n]--;
        canonical[n + 1]--;
        canonical[n + 2]++;
    }

    if (changed)
        for (int i = max(0, n - 2); i <= n + 2; i++)
            balance(i);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int N; cin >> N;
    while (N--) {
        int A; cin >> A; A--;
        canonical[A]++;
        balance(A);

        vector<int> one; // location of one digits in fibonacci representation of a number
        vector<int> distance; // distance between one digits, from the largest fibonacci number
        int last = -1;

        for (auto i : canonical) if (i.second) 
            one.push_back(i.first);

        for (auto i : one)
            distance.push_back(i - last), last = i;
        
        reverse(distance.begin(), distance.end());

        array<lint, 2> DP, nextDP;
        DP[1] = 1; DP[0] = 0; // DP[A] = DP[does the next one digit must be pushed to the left?]

        for (auto d : distance) {
            nextDP[0] = ((d % 2 == 0)? DP[0] + DP[1] : 0) % MOD;
            nextDP[1] = ((DP[0] + DP[1]) * max(0ll, (d - 1ll) / 2ll) + DP[1]) % MOD;
            DP = nextDP;
        }

        cout << DP[1] << "\n";

    }
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 10 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35