Submission #200628

#	Time	Username	Problem	Language	Result	Execution time	Memory
200628		tincamatei	Remittance (JOI19_remittance)	C++14	0 / 100	5 ms	376 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;

int A[MAX_N], B[MAX_N];
int viz[MAX_N];

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

	if(reqAmount > INF)
		return false;

	if(A[i] < reqAmount) {
		reqAmount -= A[i];
		A[i] = 0;
		if(!solveRequests((i - 1 + N) % N, reqAmount * 2, N))
			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];

int check(long long val, int N, long long overflow) {
	sent[0] = val;

	if(overflow - val < 0)
		return +1;

	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;
			return true;
		}
	}

	return false;
}

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

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

	if(!launderMoney(N))
		answerIsNo();

	printf("Yes");

	return 0;
}

Compilation message (stderr)

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

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