Submission #137992

#	Time	Username	Problem	Language	Result	Execution time	Memory
137992		sebinkim	Remittance (JOI19_remittance)	C++14	100 / 100	433 ms	24100 KiB

remittance

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

ll A[1010101], B[1010101], X[1010101];
ll n, p, q, s, a, b, x, t;

void die() { printf("No\n"); exit(0); }

ll pow(ll a, ll b)
{
	ll ret = 1;
	
	for(; b; b>>=1){
		if(b & 1) ret = ret * a % mod;
		a = a * a % mod;
	}
	
	return ret;
}

void check()
{
	ll i, j;
	
	p = (pow(2ll, n) - 1 + mod) % mod;
	q = pow(p, mod - 2);
	s = 0; x = 0; t = 0;
	
	for(i=n; i>=1; i--){
		s = (s * 2 + (A[i] - B[i]) + mod) % mod;
	}
	
	X[n] = s * q % mod;
	
	for(i=n-1; i>=1; i--){
		s = (s * 2 - (A[i + 1] - B[i + 1]) * p % mod + mod) % mod;
		X[i] = s * q % mod;
	}
		
	X[0] = X[n];
	
	for(i=1; i<=n; i++){
		x += X[i];
		if(X[i] < 0) die();
		if(A[i] + X[i - 1] - X[i] * 2 != B[i]) die();
	}
	
	if(a - b != x) die();
	
	for(j=1; j<=3; j++){
		for(i=1; i<=n; i++){
			if(A[i] >= X[i] * 2){
				A[i % n + 1] += X[i];
				A[i] -= X[i] * 2;
				X[i] = 0;
			}
			else{
				A[i % n + 1] += A[i] / 2;
				X[i] -= A[i] / 2;
				A[i] -= A[i] / 2 * 2;
			}
		}
	}
	
	for(i=1; i<=n; i++){
		if(A[i] != B[i]) die();
	}
}

int main()
{
	ll i;
	
	scanf("%lld", &n);
	
	for(i=1; i<=n; i++){
		scanf("%lld%lld", A + i, B + i);
		a += A[i]; b += B[i];
	}
	
	if(a < b) die();
	
	check();
	
	printf("Yes\n");
	
	return 0;
}

Compilation message (stderr)

remittance.cpp: In function 'int main()':
remittance.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
remittance.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", A + i, B + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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