Submission #397021

#	Time	Username	Problem	Language	Result	Execution time	Memory
397021		tibinyte	The grade (info1cup18_thegrade)	C++14	100 / 100	455 ms	6572 KiB

thegrade

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <bitset>
#include <string>
#include <unordered_map>
#pragma optimize("O2")
#define mod 1000000007
using namespace std;
long long powmod(long long a, long long b, long long p) {
	if (b == 0) {
		return 1;
	}
	if (b % 2 == 1) {
		return (a * powmod(a, b - 1, p)) % p;
	}
	long long P = powmod(a, b / 2, p);
	return (P * P) % p;
}
long long inv(long long a, long long p) {
	return powmod(a, p - 2, p);
}
vector<long long> fact;
long long combs(long long n, long long k, long long p) {
	return ((fact[n] * inv(fact[k], p) % p) * inv(fact[n - k] , p)) % p;
}
long long stars_and_bars(long long n, long long k, long long p) {
	return combs(n + k - 1, n, p);
}
void precompute(long long n , long long p) {
	fact = vector<long long>(n + 1);
	fact[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fact[i] = fact[i - 1] * i;
		fact[i] %= p;
	}
}
int main() {
	int q, n;
	cin >> q >> n;
	precompute(n, mod);
	vector<int> f(1000001);
	long long sum = 0;
	long long perms = 1;
	long long elem = 0;
	while (q--) {
		int t, x;
		cin >> t >> x;
		perms *= inv(fact[elem], mod);
		perms %= mod;
		if (t == 1) {
			perms *= fact[f[x]];
			perms %= mod;
			f[x]--;
			perms *= inv(fact[f[x]], mod);
			perms %= mod;
			elem--;
			sum -= x;
		}
		else {
			perms *= fact[f[x]];
			perms %= mod;
			f[x]++;
			perms *= inv(fact[f[x]], mod);
			perms %= mod;
			sum += x;
			elem++;
		}
		perms *= fact[elem];
		perms %= mod;
		if (sum > n) {
			cout << -1 << '\n';
			continue;
		}
		cout << (perms * stars_and_bars(n - sum, elem + 1, mod)) % mod << '\n';
	}
}

Compilation message (stderr)

thegrade.cpp:9: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
    9 | #pragma optimize("O2")
      |

• 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