Submission #93404

#	Time	Username	Problem	Language	Result	Execution time	Memory
93404		Kastanda	Fibonacci representations (CEOI18_fib)	C++11	50 / 100	4017 ms	1700 KiB

fib

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 100005, Mod = 1e9 + 7;
int n, A[N];
set < int > B;
inline void Add(int a)
{
    if (a < 0)
        return ;
    if (a == 0)
    {
        Add(1);
        return ;
    }
    if (B.count(a))
    {
        B.erase(a);
        Add(a + 1);
        Add(a - 2);
        return ;
    }
    if (B.count(a - 1))
    {
        B.erase(a - 1);
        Add(a + 1);
        return ;
    }
    if (B.count(a + 1))
    {
        B.erase(a + 1);
        Add(a + 2);
        return ;
    }
    B.insert(a);
}
inline int Solve()
{
    int a = 1, b = 0;
    for (auto it = B.begin(); it != B.end(); it ++)
    {
        int cz = (*it) - 1;
        if (it != B.begin())
        {
            it --;
            cz -= *it;
            it ++;
        }
        a = (a + b) % Mod;
        b = (1LL * (cz >> 1) * a + 1LL * (cz & 1) * b) % Mod;
    }
    return ((a + b) % Mod);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &A[i]);
        Add(A[i]);

        printf("%d\n", Solve());
    }
    return (0);
}

Compilation message (stderr)

fib.cpp: In function 'int main()':
fib.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
fib.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~

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