Submission #917176

#	Time	Username	Problem	Language	Result	Execution time	Memory
917176		MateiKing80	The grade (info1cup18_thegrade)	C++14	100 / 100	144 ms	4296 KiB

thegrade

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int mod = 1e9 + 7;
map<int, int> umap;
vector<int> fact;


int lgpow(int b, int e)
{
    if(e == 0)
        return 1;
    int x = lgpow(b, e / 2);
    if((e % 2) == 1)
        return (((x * x) % mod) * b) % mod;
    return (x * x) % mod;
}

int inv(int x)
{
    return lgpow(x, mod - 2);
}

int fct(int x)
{
    while(x >= fact.size())
        fact.push_back((fact.back() * fact.size()) % mod);
    return fact[x];
}

int comb(int k, int n)
{
    if(k < 0 || n < k)
        return 0;
    return ((fct(n) * inv(fct(k))) % mod * inv(fct(n - k))) % mod;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fact.push_back(1);
    int q, p, ori = 1, sum = 0, nr = 0;
    cin >> q >> p;
    for(int i = 0; i < q; i ++)
    {
        int t, x;
        cin >> t >> x;
        if(!t)
        {
            nr ++;
            umap[x] ++;
            sum += x;
            ori *= fct(umap[x]), ori %= mod;
            ori *= inv(fct(umap[x] - 1)), ori %= mod;
        }
        else
        {
            nr --;
            umap[x] --;
            sum -= x;
            ori *= fct(umap[x]), ori %= mod;
            ori *= inv(fct(umap[x] + 1)), ori %= mod;
        }
        //nr + 1 locuri, p - sum 0-uri
        if(!comb(nr, nr + p - sum))
            cout << -1 << '\n';
        else
            cout << ((comb(nr, nr + p - sum) * inv(ori)) % mod * fct(nr)) % mod << '\n';
    }
    return 0;
}

Compilation message (stderr)

thegrade.cpp: In function 'll fct(ll)':
thegrade.cpp:30:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     while(x >= fact.size())
      |           ~~^~~~~~~~~~~~~~

• 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