oj.uz

Submission #687701

# Submission time Handle Problem Language Result Execution time Memory
687701 2023-01-26T21:24:05 Z divad The grade (info1cup18_thegrade) C++14
25 / 100
 44 ms 3256 KB 
#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;
        nrperm *= fact[fr[x]];
        nrperm %= MOD;
        if(t == 0){
            n++;
            sum += x;
            fr[x]++;
        }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
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 388 KB Output is correct
2 Correct 43 ms 2504 KB Output is correct
3 Correct 43 ms 2524 KB Output is correct
4 Correct 42 ms 2580 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 15.0

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

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 388 KB Output is correct
2 Correct 43 ms 2504 KB Output is correct
3 Correct 43 ms 2524 KB Output is correct
4 Correct 42 ms 2580 KB Output is correct
5 Correct 43 ms 2940 KB Output is correct
6 Correct 43 ms 2996 KB Output is correct
7 Correct 44 ms 3256 KB Output is correct
8 Correct 42 ms 3024 KB Output is correct

Subtask #7
0 / 20.0

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