답안 #653768

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653768 2022-10-28T03:17:58 Z GusterGoose27 Žarulje (COI15_zarulje) C++11
0 / 100
181 ms 17896 KB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int MOD = 1e9+7;
const int MAXN = 2e5+4;
int powers[MAXN];
int dp[MAXN];
int skip_dp[MAXN];
int ans[MAXN];
int fac[MAXN];
int facinv[MAXN];
pii cur_space[MAXN];
int n, q;

int bash(pii range) {
	if (range == pii(1, n-2)) return 1;
	if (powers[range.first-1] == powers[range.second+1])
		return (bash(pii(range.first-1, range.second))+bash(pii(range.first, range.second+1)) % MOD);
	if (powers[range.first-1] > powers[range.second+1]) return bash(pii(range.first-1, range.second));
	return bash(pii(range.first, range.second+1));
}

int expo(ll a, int b) {
	ll res = 1;
	while (b > 0) {
		if (b & 1) {
			res *= a;
			res %= MOD;
		}
		b >>= 1;
		a *= a;
		a %= MOD;
	}
	return res;
}

int c(int n, int k) {
	ll cur = fac[n];
	cur *= facinv[k];
	cur %= MOD;
	cur *= facinv[n-k];
	return (cur%MOD);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> q;
	n += 2;
	fac[0] = 1;
	ll cur = 1;
	facinv[0] = 1;
	for (int i = 1; i <= n; i++) {
		cur *= i;
		cur %= MOD;
		fac[i] = cur;
		facinv[i] = expo(fac[i], MOD-2);
	}
	powers[0] = 0;
	powers[n-1] = 0;
	vector<pii> proc_order;
	for (int i = 1; i < n-1; i++) {
		cin >> powers[i];
		assert(powers[i] > 0);
		proc_order.push_back(pii(powers[i], i));
	}
	sort(proc_order.begin(), proc_order.end());
	set<int> completed_vals;
	dp[0] = dp[n-1] = 1;
	completed_vals.insert(0);
	completed_vals.insert(n-1);
	for (int r = 0; r < n-2;) {
		vector<int> to_add;
		vector<int> extra_consid;
		int l = r;
		while (r < n-2 && proc_order[l].first == proc_order[r].first) r++;
		for (int curr = l; curr < r;) {
			int curl = curr;
			auto it = completed_vals.upper_bound(proc_order[curl].second);
			int rp = *it;
			it--;
			int lp = *it;
			vector<int> cur_posses;
			while (curr < r && *completed_vals.upper_bound(proc_order[curr].second) == rp) {
				cur_posses.push_back(proc_order[curr].second);
				to_add.push_back(proc_order[curr].second);
				curr++;
			}
			cur_space[rp].first = cur_space[lp].second = cur_posses.size();
			extra_consid.push_back(lp);
			extra_consid.push_back(rp);
			for (int p = 0; p < cur_posses.size(); p++) {
				int i = cur_posses[p];
				ll curdp = dp[lp];
				curdp *= c(cur_posses.size(), p+1);
				curdp %= MOD;
				dp[i] = curdp;
				curdp = dp[lp];
				curdp *= c(cur_posses.size()-1, p);
				curdp %= MOD;
				ans[i] = curdp;
				if (p < cur_posses.size()-1) {
					curdp = dp[lp];
					curdp *= c(cur_posses.size()-1, p+1);
					curdp %= MOD;
					skip_dp[i] = curdp;
				}
			}
		}
		for (int m: extra_consid) {
			if (cur_space[m].first != 0 && cur_space[m].second != 0) {
				auto it = completed_vals.lower_bound(m);
				int lp = *(--it);
				ll curdp;
				if (powers[lp] == powers[m]) curdp = skip_dp[lp];
				else curdp = dp[lp];
				curdp *= c(cur_space[m].first+cur_space[m].second, cur_space[m].first);
				curdp %= MOD;
				ans[m] = curdp;
			}
			cur_space[m] = pii(0, 0);
		}
		for (int v: to_add) completed_vals.insert(v);
	}
	bool fail = 0;
	for (int i = 0; i < q; i++) {
		int x; cin >> x;
		//int b = bash(pii(x, x));
		cout << ans[x] << /*" " << b << */"\n";
		//if (b != ans[x]) fail = 1;
	}
	if (fail) cout << "FAIL\n";
}

Compilation message

zarulje.cpp: In function 'int main()':
zarulje.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    for (int p = 0; p < cur_posses.size(); p++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~
zarulje.cpp:105:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     if (p < cur_posses.size()-1) {
      |         ~~^~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 8836 KB Output is correct
2 Incorrect 181 ms 17896 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -