Submission #441108

#	Time	Username	Problem	Language	Result	Execution time	Memory
441108		mosesmayer	Remittance (JOI19_remittance)	C++17	100 / 100	463 ms	44216 KiB

remittance

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define int LL
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef vector<int> vi;

const LL LINF = 1e18;
const int mxsz = 1e6 + 5;
int n;
int a[mxsz], b[mxsz];
int d[mxsz];

int32_t main(){
	scanf("%lld", &n);
	for (int i = 0; i < n; i++)
		scanf("%lld %lld", a+i, b+i);
	LL dbt = 0, zeroed = 0, topup = 0, neg = 0;
	LL totalTopup = 0;
	for (int i = 0; i < n; i++){
		d[i] = a[i] - b[i];
		if (d[i] > 0) topup++, totalTopup += d[i];
		else if (d[i] < 0) neg++;
	}
#ifdef DEBUG
	for (int i = 0; i < n; i++){
		cout << i << ": " << d[i] << '\n';
	}
#endif
	bool can = 1;
	for (int i = 0; neg > 0 || dbt < 0; (i += n-1) %= n){
		dbt <<= 1;
#ifdef DEBUG
		cout << i << ' ' << dbt << ' ' << topup << ' ' << neg << '\n';
#endif
		if (topup == 0){can = 0; break;}
		if (d[i] < 0){
			dbt += d[i]; neg--;
			d[i] = 0;
		} else if (d[i] > 0){
			if (dbt < 0){
				LL x = min(llabs(dbt), 1LL * d[i]);
				dbt += x;
				d[i] -= x;
				if (d[i] == 0) topup--;
			}
		}
		if (dbt < (-LINF)){can = 0; break;}
	}
	if (can && topup > 0){
#ifdef DEBUG
		cout << "topup available\n";
		for (int i = 0; i < n; i++){
			cout << i << ": " << d[i] << '\n';
		}
#endif
		int cur = 0;
		int extra = 0;
		for (int i = 0; i < n; i++) extra += d[i];
		for (int i = 0; cur++ < n + 10 && extra > 0; (i += 1)%=n){
			if (d[i] > 1){
				int x = d[i];
				d[i] -= x;
				extra -= x; extra += __builtin_popcount(x);
				cur = 0;
				for (int b = 0; (1<<b) <= x; b++){
					if (x & (1<<b)) d[(i + b) % n]++;
				}
			}
		}
		bool sabi = 1, pinjem = 0;
		for (int i = 0; i < n; i++){
			sabi &= d[i] == 1;
			pinjem |= b[i] > 0;
		}
		if (extra > 0 && !(sabi && pinjem))  can = 0;
	}
	puts(can ? "Yes" : "No");
	return 0;
}

Compilation message (stderr)

remittance.cpp: In function 'int32_t main()':
remittance.cpp:21:14: warning: unused variable 'zeroed' [-Wunused-variable]
   21 |  LL dbt = 0, zeroed = 0, topup = 0, neg = 0;
      |              ^~~~~~
remittance.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
remittance.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%lld %lld", a+i, b+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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