Submission #159760

#	Time	Username	Problem	Language	Result	Execution time	Memory
159760		gs14004	Remittance (JOI19_remittance)	C++17	100 / 100	760 ms	52160 KiB

remittance

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
#define sz(v) ((int)(v).size())
const int MAXN = 1000005;

int n;
lint a[MAXN], b[MAXN], f[MAXN];

void my_ass(bool p){
	if(!p){
		puts("No");
		exit(0);
	}
}

int main(){
	scanf("%d",&n);
	vector<lint> need(n);
	for(int i=0; i<n; i++){
		scanf("%lld %lld",&a[i],&b[i]);
		need[i] = b[i] - a[i];
	}
	if(count(need.begin(), need.end(), 0) == n){
		puts("Yes");
		return 0;
	}
	for(int i=0; i<30; i++){
		for(int j=0; j<n; j++){
			if(need[j] & 1){
				f[j] += (1ll << i);
				need[j]--;
				need[(j+n-1)%n] += 2;
			}
		}
		for(int j=0; j<n; j++) need[j] >>= 1;
	}
	lint tot_bal = *min_element(f, f + n);
	int pos = min_element(f, f + n) - f;
	rotate(a, a + pos, a + n);
	rotate(b, b + pos, b + n);
	for(int i=0; i<n; i++) b[i] += tot_bal;
	for(int i=0; i<n; i++){
		lint toSend = a[i] - b[i];
		if(i == n - 1) my_ass(toSend == 0);
		my_ass(toSend >= 0 && toSend % 2 == 0);
		a[i + 1] += toSend / 2;
		a[i] -= toSend;
	}
	bool good = 0;
	for(int i=0; i<n; i++){
		my_ass(a[i] >= tot_bal);
		if(a[i] > tot_bal) good = 1;
	}
	my_ass(good);
	puts("Yes");
}

Compilation message (stderr)

remittance.cpp: In function 'int main()':
remittance.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
remittance.cpp:22: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