oj.uz

Submission #254872

# Submission time Handle Problem Language Result Execution time Memory
254872 2020-07-30T18:57:55 Z MarcoMeijer Fibonacci representations (CEOI18_fib) C++14
50 / 100
 4000 ms 9840 KB 
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }

// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi," ",x.se);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }

//===================//
//  Added libraries  //
//===================//

// mod library
ll MOD=1e9+7;

inline ll mod(ll x_) {
    return (x_)%MOD;
}
ll modpow(ll x_, ll N_) {
    if(N_ == 0) return 1;
    ll a = modpow(x_,N_/2);
    a = (a*a)%MOD;
    if(N_%2) a = (a*x_)%MOD;
    return a;
}
ll inv(ll x_) {
    return modpow(x_, MOD-2);
}
class mi {
public:
    mi(ll v=0) {value = v;}
    mi  operator+ (ll rs) {return mod(value+rs);}
    mi  operator- (ll rs) {return mod(value-rs+MOD);}
    mi  operator* (ll rs) {return mod(value*rs);}
    mi  operator/ (ll rs) {return mod(value*inv(rs));}
    mi& operator+=(ll rs) {*this = (*this)+rs; return *this;}
    mi& operator-=(ll rs) {*this = (*this)-rs; return *this;}
    mi& operator*=(ll rs) {*this = (*this)*rs; return *this;}
    mi& operator/=(ll rs) {*this = (*this)/rs; return *this;}
    operator ll&() {return value;}

    ll value;
};
typedef vector<mi> vmi;

//===================//
//end added libraries//
//===================//

void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}


//===================//
//   begin program   //
//===================//

const int MX = 5e5;
int n, a[MX];
map<int, int> mp;
set<int> inq;
queue<int> q;
int p[MX], m;
mi dp[MX][2];
bool findingPositions = 1;
set<int> positions;

void tryAdd(int x) {
    if(inq.count(x)) return;
    if(findingPositions) positions.insert(x);
    int am = mp[x];
    if(am >= 2) {
        q.push(x);
        inq.insert(x);
    }
    else if(am == 1) {
        if(mp.count(x-1) && mp[x-1] == 1) {
            q.push(x);
            inq.insert(x);
        }
        if(mp.count(x+1) && mp[x+1] == 1) {
            q.push(x+1);
            inq.insert(x+1);
        }
    }
}
void fix(int x) {
    int am = mp[x];
    if(am >= 2) {
        int times = am/2;
        if(am%2) mp[x] = 1;
        else mp.erase(x);
        if(x >= 3) {
            mp[x-2] += times;
            mp[x+1] += times;
            tryAdd(x-2);
            tryAdd(x+1);
        }
        if(x == 2) {
            mp[1] += times;
            mp[3] += times;
            tryAdd(1);
            tryAdd(3);
        }
        if(x == 1) {
            mp[2] += times;
            tryAdd(2);
        }
        tryAdd(x);
    } else {
        int oam = mp.count(x-1) ? mp[x-1] : 0;
        if(am == 1 && oam>=1) {
            mp[x-1]--;
            mp[x]--;
            if(oam == 1) mp.erase(x-1);
            mp.erase(x);
            mp[x+1]++;
            tryAdd(x+1);
        }
    }
}

mi cAns;
set<int> numbers;

struct M {
    mi m[2][2];
    mi* operator [] (int i) {return m[i];}
    M operator* (M& rhs) {
        M ans;
        RE(i,2) RE(j,2) RE(k,2) ans[i][j] += m[i][k]*rhs[k][j];
        return ans;
    }
};
struct S {
    int bg, ed;
    M m;
    S(int p = -1) {
        bg = p, ed = p;
        m[0][0] = 1;
        m[1][1] = 1;
        m[0][1] = 0;
        m[1][0] = 0;
    }
    S(S& l, S& r) {
        if(l.bg == -1) {
            *this = r;
            return;
        }
        if(r.bg == -1) {
            *this = l;
            return;
        }
        int dist = r.bg-l.ed;
        M mid;
        bg = l.bg;
        ed = r.ed;
        if((dist%2) == 0) {
            mid.m[0][0] = 1;
            mid.m[0][1] = 1;
        }
        mid.m[1][0] = mi((dist-1)/2);
        mid.m[1][1] = mi((dist-1)/2 + 1);

        m = (l.m * mid) * r.m;
    }
};

void program() {
    IN(n);
    RE(i,n) IN(a[i]);

    RE(i,n) {
        mp[a[i]]++;
        tryAdd(a[i]);
        while(!q.empty()) {
            int p = q.front(); q.pop();
            fix(p);
            inq.erase(p);
        }

        int m=0;
        for(auto it=mp.begin(); it!=mp.end(); it++)
            p[m++] = it->fi;

        S ans(0);
        dp[0][0] = 0;
        dp[0][1] = 1;
        RE(j,m) {
            S cur(p[j]);
            ans = S(ans,cur);
        }
        OUTL(ll(ans.m[1][1]));
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8192 KB Output is correct
2 Execution timed out 4070 ms 9840 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

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