oj.uz

Submission #161421

# Submission time Handle Problem Language Result Execution time Memory
161421 2019-11-02T10:34:38 Z rama_pang Fibonacci representations (CEOI18_fib) C++14
50 / 100
 4000 ms 2640 KB 
#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.0 / 5.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Execution timed out 4022 ms 2640 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 380 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 4 ms 376 KB Output is correct
21 Correct 4 ms 376 KB Output is correct
22 Correct 3 ms 376 KB Output is correct
23 Correct 3 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Execution timed out 4022 ms 2640 KB Time limit exceeded
26 Halted 0 ms 0 KB -