제출 #483303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483303		Monarchuwu	Fibonacci representations (CEOI18_fib)	C++17	50 / 100	2339 ms	428 KiB

fib

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 100 + 2, mod = 1e9 + 7;
int n, a[N];

ll dp[N][2];
ll calc(map<int, int> mp) {
    vector<int> v(1, 0);
    for (auto i : mp) v.push_back(i.ff);

    int n = mp.size();
    dp[0][0] = 1;
    for (int i = 1, dist; i <= n; ++i) {
        dist = v[i] - v[i - 1];
        (dp[i][0] = dp[i - 1][0] + dp[i - 1][1]) %= mod;
        (dp[i][1] = dp[i - 1][0] * ((dist - 1) / 2) + dp[i - 1][1] * (dist / 2)) %= mod;
    }
    return (dp[n][0] + dp[n][1]) % mod;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    map<int, int> mp;
    for (int i = 1; i <= n; ++i) {
        ++mp[a[i]];

        set<int> s;
        s.insert(a[i]);
        while (!s.empty()) {
            int x = *s.begin(); s.erase(s.begin());

            if (mp[x] == 2) {
                if (x == 1) {
                    ++mp[x + 1];
                    s.insert(x + 1);
                }
                else if (x == 2) {
                    ++mp[x + 1], ++mp[x - 1];
                    s.insert(x + 1), s.insert(x - 1);
                }
                else {
                    ++mp[x + 1], ++mp[x - 2];
                    s.insert(x + 1), s.insert(x - 2);
                }
                mp.erase(x);
            }
            else {
                if (mp.count(x - 1)) {
                    mp.erase(x - 1), mp.erase(x);
                    ++mp[x + 1];
                    s.insert(x + 1);
                }
                else if (mp.count(x + 1)) {
                    mp.erase(x), mp.erase(x + 1);
                    ++mp[x + 2];
                    s.insert(x + 2);
                }
            }
        }
        cout << calc(mp) << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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