oj.uz

Submission #483303

# Submission time Handle Problem Language Result Execution time Memory
483303 2021-10-28T15:05:45 Z Monarchuwu Fibonacci representations (CEOI18_fib) C++17
50 / 100
 2339 ms 428 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 316 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 312 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2339 ms 428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 316 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 312 KB Output is correct
24 Runtime error 2339 ms 428 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -