Submission #223590

#	Time	Username	Problem	Language	Result	Execution time	Memory
223590		spacewalker	Remittance (JOI19_remittance)	C++14	100 / 100	588 ms	28024 KiB

remittance

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;

ll FMOD(ll x) {
	return (x % MOD + MOD) % MOD;
}

// if X, the next number will be
// 2X - peak

void answer(bool yn) {
	if (yn) printf("Yes\n");
	else printf("No\n");
	exit(0);
}

ll modexp(ll b, ll e) {
	if (e == 0) return 1;
	else return (e & 1 ? b : 1) * modexp(b * b % MOD, e/2) % MOD;
}

ll modinv(ll x) {return modexp(x, MOD - 2);}

int main() {
	int n; scanf("%d", &n);
	vector<ll> before(n), after(n);
	for (int i = 0; i < n; ++i) scanf("%lld %lld", &before[i], &after[i]);
	ll sanity = 0;
	for (int i = 0; i < n; ++i) if (before[i] != after[i]) ++sanity;
	if (sanity == 0) answer(true);
	sanity = 0;
	for (int x : after) sanity += x;
	if (sanity == 0) answer(false);
	vector<ll> flows(n);
	for (int i = 0; i < n; ++i) flows[n-1] = FMOD(flows[n-1] + modexp(2, i) * (before[i] - after[i]));
	flows[n-1] = FMOD(flows[n-1] * modinv(FMOD(modexp(2, n) - 1)));
	for (int i = n - 2; i >= 0; --i) flows[i] = FMOD(2*flows[i+1] - (before[i + 1] - after[i + 1]));
	for (int i = 0; i < n; ++i) {
		if (2*flows[i] - flows[(i + n - 1) % n] != before[i] - after[i]) answer(false);
	}
//	for (int i = 0; i < n; ++i) printf("%d flow %lld\n", i, flows[i]);
	answer(true);
	return 0;

}

Compilation message (stderr)

remittance.cpp: In function 'int main()':
remittance.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
remittance.cpp:30:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < n; ++i) scanf("%lld %lld", &before[i], &after[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45