Submission #972443

#	Time	Username	Problem	Language	Result	Execution time	Memory
972443		Charizard2021	Fibonacci representations (CEOI18_fib)	C++17	50 / 100	4086 ms	3572 KiB

fib

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
map<int, int> mp;
void getValues(int x){
    if(mp[x] != 0){
        if(mp[x] == 1){
            if(x >= 1 && mp[x - 1] != 0){
                mp[x - 1]--;
                mp[x]--;
                mp[x + 1]++;
                getValues(x + 1);
            }
            else if(mp[x + 1] != 0) {
                mp[x]--;
                mp[x + 1]--;
                mp[x + 2]++;
                getValues(x + 2);
            }
        }
        else{
            mp[x] = 0;
            mp[x + 1]++;
            getValues(x + 1);
            if(x > 1){
                mp[x - 2]++;
                getValues(x - 2);
            }
            else if(x == 1){
                mp[0]++;
                getValues(0);
            }
        }
    }
}
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        x--;
        mp[x]++;
        getValues(x);
        vector<long long> a;
        for(auto it : mp){
            if(it.second != 0){
                a.push_back(it.first);
            }
        }
        vector<long long> dp((int)a.size());
        dp[0] = a[0]/2;
        int ans = 1;
        for(int j = 1; j < (int)a.size(); j++){
            dp[j] = ((a[j] - a[j - 1])/2LL * dp[j - 1] + (a[j] - a[j - 1] - 1)/2LL * ans) % MOD;
            ans += dp[j - 1];
            ans %= MOD;
        }
        cout << (ans + dp.back()) % MOD << "\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