Submission #200631

#	Time	Username	Problem	Language	Result	Execution time	Memory
200631		tincamatei	Remittance (JOI19_remittance)	C++14	55 / 100	387 ms	43640 KiB

remittance

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;
const int INF = 1000000000;
const long long INFLL = (long long)MAX_N * INF;

long long A[MAX_N], B[MAX_N];
bool viz[MAX_N];
long long finalSent[MAX_N];

bool solveRequests(int i, int reqAmount, int N, bool addSent = false) {
	if(viz[i])
		return false;
	viz[i] = true;

	if(reqAmount > INF)
		return false;
	
	if(addSent)
		finalSent[i] += reqAmount / 2;

	if(A[i] < reqAmount) {
		reqAmount -= A[i];
		A[i] = 0;
		if(!solveRequests((i - 1 + N) % N, reqAmount * 2, N, true))
			return false;
	} else {
		A[i] -= reqAmount;
	}

	viz[i] = false;
	return true;
}

void answerIsNo() {
	printf("No");
	exit(0);
}

// A[i] - 2 * sent[i] + sent[i - 1] == 0
// A[i] == 2 * sent[i] - sent[i - 1]

long long sent[MAX_N];
long long Ac[MAX_N];

int check(long long val, int N, long long overflow) {
	sent[0] = val;
	
	if(overflow - val < 0)
		return +1;
	overflow -= val;

	for(int i = 1; i < N; ++i) {
		// A[i] = 2 * sent[i] - sent[i - 1]
		// sent[i] = (A[i] + sent[i - 1]) / 2
		
		sent[i] = (A[i] + sent[i - 1]) / 2;
		overflow -= sent[i];
		if(overflow < 0)
			return +1;
	}
	
	if(overflow < 0)
		return +1;
	else if(overflow > 0)
		return -1;
	return 0;
}

bool launderMoney(int N) {
	long long st = -1, dr = INFLL + 1;
	long long overflow = 0LL;

	for(int i = 0; i < N; ++i)
		overflow += A[i];

	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		int rez = check(mid, N, overflow);
		if(rez == -1) // Too small
			st = mid;
		else if(rez == 1) // Too big
			dr = mid;
		else { // perfect
			for(int i = 0; i < N; ++i) {
				if(A[i] != 2 * sent[i] - sent[(i - 1 + N) % N])
					return false;
				finalSent[i] += sent[i];
			}
			return true;
		}
	}

	return false;
}

bool checkSent(int N) {
	for(int _i = 0; _i < 3 * N; ++_i) {
		int i = _i % N;
		long long send = min(finalSent[i], Ac[i] / 2);
		Ac[i] -= 2 * send;
		Ac[(i + 1) % N] += send;
		finalSent[i] -= send;
	}

	for(int i = 0; i < N; ++i)
		if(finalSent[i] != 0 || Ac[i] != B[i])
			return false;
	return true;
}

int main() {
	int N;
	
	scanf("%d", &N);
	
	for(int i = 0; i < N; ++i) {
		scanf("%lld%lld", &A[i], &B[i]);
		Ac[i] = A[i];
	}

	for(int i = 0; i < N; ++i) {
		if(!solveRequests(i, B[i], N))
			answerIsNo();
	}
	
	if(!launderMoney(N))
		answerIsNo();

	if(!checkSent(N))
		answerIsNo();

	printf("Yes");

	return 0;
}

Compilation message (stderr)

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