oj.uz

Submission #96040

# Submission time Handle Problem Language Result Execution time Memory
96040 2019-02-05T10:52:30 Z alextodoran The grade (info1cup18_thegrade) C++14
100 / 100
 326 ms 18488 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 16120 KB Output is correct
2 Correct 268 ms 15992 KB Output is correct
3 Correct 273 ms 16024 KB Output is correct
4 Correct 273 ms 15992 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 16128 KB Output is correct
2 Correct 315 ms 16648 KB Output is correct
3 Correct 315 ms 16892 KB Output is correct
4 Correct 317 ms 16900 KB Output is correct
5 Correct 320 ms 16624 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 16092 KB Output is correct
2 Correct 324 ms 17556 KB Output is correct
3 Correct 319 ms 17360 KB Output is correct
4 Correct 321 ms 17416 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 16120 KB Output is correct
2 Correct 268 ms 15992 KB Output is correct
3 Correct 273 ms 16024 KB Output is correct
4 Correct 273 ms 15992 KB Output is correct
5 Correct 271 ms 16128 KB Output is correct
6 Correct 315 ms 16648 KB Output is correct
7 Correct 315 ms 16892 KB Output is correct
8 Correct 317 ms 16900 KB Output is correct
9 Correct 320 ms 16624 KB Output is correct
10 Correct 267 ms 16092 KB Output is correct
11 Correct 324 ms 17556 KB Output is correct
12 Correct 319 ms 17360 KB Output is correct
13 Correct 321 ms 17416 KB Output is correct
14 Correct 274 ms 16092 KB Output is correct
15 Correct 313 ms 17372 KB Output is correct
16 Correct 310 ms 17436 KB Output is correct
17 Correct 313 ms 17400 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 16128 KB Output is correct
2 Correct 315 ms 16648 KB Output is correct
3 Correct 315 ms 16892 KB Output is correct
4 Correct 317 ms 16900 KB Output is correct
5 Correct 320 ms 16624 KB Output is correct
6 Correct 313 ms 17052 KB Output is correct
7 Correct 313 ms 17116 KB Output is correct
8 Correct 317 ms 17576 KB Output is correct
9 Correct 319 ms 17656 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 16092 KB Output is correct
2 Correct 324 ms 17556 KB Output is correct
3 Correct 319 ms 17360 KB Output is correct
4 Correct 321 ms 17416 KB Output is correct
5 Correct 316 ms 17992 KB Output is correct
6 Correct 317 ms 18052 KB Output is correct
7 Correct 326 ms 18488 KB Output is correct
8 Correct 315 ms 18048 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 16120 KB Output is correct
2 Correct 268 ms 15992 KB Output is correct
3 Correct 273 ms 16024 KB Output is correct
4 Correct 273 ms 15992 KB Output is correct
5 Correct 271 ms 16128 KB Output is correct
6 Correct 315 ms 16648 KB Output is correct
7 Correct 315 ms 16892 KB Output is correct
8 Correct 317 ms 16900 KB Output is correct
9 Correct 320 ms 16624 KB Output is correct
10 Correct 267 ms 16092 KB Output is correct
11 Correct 324 ms 17556 KB Output is correct
12 Correct 319 ms 17360 KB Output is correct
13 Correct 321 ms 17416 KB Output is correct
14 Correct 274 ms 16092 KB Output is correct
15 Correct 313 ms 17372 KB Output is correct
16 Correct 310 ms 17436 KB Output is correct
17 Correct 313 ms 17400 KB Output is correct
18 Correct 313 ms 17052 KB Output is correct
19 Correct 313 ms 17116 KB Output is correct
20 Correct 317 ms 17576 KB Output is correct
21 Correct 319 ms 17656 KB Output is correct
22 Correct 316 ms 17992 KB Output is correct
23 Correct 317 ms 18052 KB Output is correct
24 Correct 326 ms 18488 KB Output is correct
25 Correct 315 ms 18048 KB Output is correct
26 Correct 321 ms 17712 KB Output is correct
27 Correct 317 ms 17592 KB Output is correct
28 Correct 318 ms 17656 KB Output is correct
29 Correct 318 ms 17528 KB Output is correct
30 Correct 318 ms 17584 KB Output is correct