Submission #96040

#	Time	Username	Problem	Language	Result	Execution time	Memory
96040		alextodoran	The grade (info1cup18_thegrade)	C++14	100 / 100	326 ms	18488 KiB

thegrade

#include <bits/stdc++.h>

#define NRM 1000002
#define ll long long

using namespace std;

const ll MOD = 1e9+7;

ll pwr (ll a, ll b)
{
    if(b == 0)
        return 1;
    ll p = pwr(a, b / 2);
    if(b & 1)
        return p * p % MOD * a % MOD;
    return p * p % MOD;
}

ll inv (ll x)
{
    return pwr(x, MOD - 2);
}

int q, n;

ll vf[NRM];
ll nr, sum;

ll perm = 1;

ll fact[NRM], invfact[NRM];

ll comb(ll a, ll b)
{
    return fact[a] * invfact[b] % MOD * invfact[a - b] % MOD;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> q >> n;
    fact[0] = 1;
    for(int i = 1; i <= 1e6; i++)
        fact[i] = fact[i - 1] * i % MOD;
    for(int i = 0; i <= 1e6; i++)
        invfact[i] = pwr(fact[i], MOD - 2);
    while(q--)
    {
        int op, val;
        cin >> op >> val;
        if(op == 0)
        {
            vf[val]++;
            nr++;
            perm = perm * nr % MOD * inv(vf[val]) % MOD;
            sum += val;
            ll ans;
            if(sum > n)
                ans = 0;
            else
                ans = perm * comb(n - sum + nr, n - sum) % MOD;
            if(ans == 0)
                cout << "-1\n";
            else
                cout << ans << "\n";
        }
        else
        {
            perm = perm * inv(nr) % MOD * vf[val] % MOD;
            vf[val]--;
            nr--;
            sum -= val;
            ll ans;

            if(sum > n)
                ans = 0;
            else
                ans = perm * comb(n - sum + nr, n - sum) % MOD;
            if(ans == 0)
                cout << "-1\n";
            else
                cout << ans << "\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