oj.uz

Submission #96039

# Submission time Handle Problem Language Result Execution time Memory
96039 2019-02-05T10:49:21 Z alextodoran The grade (info1cup18_thegrade) C++14
20 / 100
 373 ms 17656 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 = 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 = 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 266 ms 16120 KB Output is correct
2 Correct 268 ms 15992 KB Output is correct
3 Correct 271 ms 16060 KB Output is correct
4 Correct 270 ms 15996 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 16060 KB Output is correct
2 Correct 316 ms 17072 KB Output is correct
3 Correct 312 ms 17656 KB Output is correct
4 Correct 309 ms 17608 KB Output is correct
5 Correct 310 ms 17144 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 266 ms 16120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 16120 KB Output is correct
2 Correct 268 ms 15992 KB Output is correct
3 Correct 271 ms 16060 KB Output is correct
4 Correct 270 ms 15996 KB Output is correct
5 Correct 270 ms 16060 KB Output is correct
6 Correct 316 ms 17072 KB Output is correct
7 Correct 312 ms 17656 KB Output is correct
8 Correct 309 ms 17608 KB Output is correct
9 Correct 310 ms 17144 KB Output is correct
10 Incorrect 266 ms 16120 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 16060 KB Output is correct
2 Correct 316 ms 17072 KB Output is correct
3 Correct 312 ms 17656 KB Output is correct
4 Correct 309 ms 17608 KB Output is correct
5 Correct 310 ms 17144 KB Output is correct
6 Correct 311 ms 17580 KB Output is correct
7 Incorrect 373 ms 17528 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 266 ms 16120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 16120 KB Output is correct
2 Correct 268 ms 15992 KB Output is correct
3 Correct 271 ms 16060 KB Output is correct
4 Correct 270 ms 15996 KB Output is correct
5 Correct 270 ms 16060 KB Output is correct
6 Correct 316 ms 17072 KB Output is correct
7 Correct 312 ms 17656 KB Output is correct
8 Correct 309 ms 17608 KB Output is correct
9 Correct 310 ms 17144 KB Output is correct
10 Incorrect 266 ms 16120 KB Output isn't correct
11 Halted 0 ms 0 KB -