Submission #687702

#	Time	Username	Problem	Language	Result	Execution time	Memory
687702		divad	The grade (info1cup18_thegrade)	C++14	100 / 100	50 ms	3324 KiB

thegrade

#include <bits/stdc++.h>
#define int long long
#define NMAX 1000002
#define FMAX 100002
#define MOD  1000000007
using namespace std;
int fr[NMAX],fact[FMAX],invfact[FMAX],nrperm;
int q,p,t,x,n,sum;

int lgput(int n, int a){
    if(a == 0){
        return 1;
    }else{
        if(a%2 == 0){
            int val = lgput(n, a/2);
            return (val*val)%MOD;
        }else{
            return (n*lgput(n, a-1))%MOD;
        }
    }
}

int comb(int n, int m){
    return ((fact[n]*invfact[m])%MOD*invfact[n-m])%MOD;
}

int stars_and_bars(int n, int k){
    return comb(n+k-1, k-1);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> q >> p;
    fact[0] = 1;
    invfact[0] = lgput(fact[0], MOD-2);
    for(int i = 1; i <= q; i++){
        fact[i] = fact[i-1]*i;
        fact[i] %= MOD;
        invfact[i] = lgput(fact[i], MOD-2);
    }
    nrperm = 1;
    while(q--){
        cin >> t >> x;
        nrperm *= invfact[n];
        nrperm %= MOD;
        if(t == 0){
            nrperm *= fact[fr[x]];
            nrperm %= MOD;
            n++;
            sum += x;
            fr[x]++;
            nrperm *= invfact[fr[x]];
            nrperm %= MOD;
        }else{
            nrperm *= fact[fr[x]];
            nrperm %= MOD;
            n--;
            sum -= x;
            fr[x]--;
            nrperm *= invfact[fr[x]];
            nrperm %= MOD;
        }
        nrperm *= fact[n];
        nrperm %= MOD;
        if(sum > p){
            /// nu putem sa le distantam
            cout << "-1\n";
            continue;
        }
        /// p-sum = cu cate ne putem juca
        /// nrperm = nr de permutari distincte din A
        cout << (nrperm * stars_and_bars(p-sum, n+1))%MOD << "\n";
    }
    return 0;
}

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