oj.uz

Submission #223583

# Submission time Handle Problem Language Result Execution time Memory
223583 2020-04-15T14:04:31 Z spacewalker Remittance (JOI19_remittance) C++14
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// if X, the next number will be
// 2X - peak

vector<ll> canonBinary(vector<ll> &arr) {
	vector<ll> ans = arr;
	for (int i = 0; i < 40; ++i) ans.push_back(0);
	for (int i = 0; i + 1 < ans.size(); ++i) {
		ans[i + 1] += ans[i] / 2;
		ans[i] %= 2;
	}
	return ans;
}

void answer(bool yn) {
	if (yn) printf("Yes\n");
	else printf("No\n");
	exit(0);
}

ll tryDivide(vector<ll> digs, ll n) {
	// Attempts to return digs / (2 ^ n - 1), returns -1 if that is not an integer
	// NUMBERS HERE ARE MOST SIGNIFICANT FIRST
	vector<ll> curRem;
	int curRemDigitSum = 0;
	vector<ll> ans;
	for (int d : digs) {
		if (curRem.empty() && d == 0) {
			ans.push_back(0);
			continue;
		}
		curRem.push_back(d);
		curRemDigitSum += d;
		if (curRem.size() < n || (curRem.size() == n && curRemDigitSum < n)) {
//			printf("zero added\n");
			ans.push_back(0);
		} else {
			ans.push_back(1);
			// update curRem to be curRem - (2 ^ n - 1)
//			printf("DIVIDE INITIATED:\n");
//			for (int x : curRem) printf("%d", x);
//			printf("\n");
			fflush(stdout);
			if (curRem.size() == n) {
				curRem.clear();
				curRemDigitSum = 0;
			} else {
				for (int i = 1; i <= n; ++i) curRem[i] -= 1;
				int recentOne = -1;
				for (int i = 0; i <= n; ++i) {
					if (curRem[i] == 1) recentOne = i;
					else if (curRem[i] == -1) {
						curRem[recentOne] = 0;
						for (int j = recentOne + 1; j <= i; ++j) {
							curRem[j] = 1;
						}
						recentOne = i;
					}
				}
				int fone = -1;
				for (int i = 0; i <= n; ++i) {
					if (curRem[i] == 1) {
						fone = i; break;
					}
				}
				curRemDigitSum = 0;
				if (fone == -1) {
					curRem.clear();
				} else {
					curRem = vector<ll>(begin(curRem) + fone, end(curRem));
					for (int x : curRem) curRemDigitSum += x;
				}
			}
		}
	}
	if (curRemDigitSum == 0) {
		ll numerical = 0;
		for (int x : ans) numerical = 2 * numerical + x;
		return numerical;
	} else return -1;
}

int main() {
	int n; scanf("%d", &n);
	vector<ll> before(n), after(n);
	for (int i = 0; i < n; ++i) scanf("%lld %lld", &before[i], &after[i]);
	vector<ll> beforeConv = canonBinary(before), afterConv = canonBinary(after);
	vector<ll> difference(beforeConv.size(), 0);
	int diffLen = difference.size();
//	for (int i = diffLen - 1; i >= 0; --i) printf("%lld", beforeConv[i]);
//	printf("\n");
//	for (int i = diffLen - 1; i >= 0; --i) printf("%lld", afterConv[i]);
//	printf("\n");
	for (int i = 0; i < diffLen; ++i) difference[i] = beforeConv[i] - afterConv[i];
//	for (int i = diffLen - 1; i >= 0; --i) printf("%lld", difference[i]);
//	printf("\n");
	bool earlyNegativeBreak = false;
	int recentOne = -1;
	for (int i = diffLen - 1; i >= 0; --i) {
		if (difference[i] == 1) recentOne = i;
		else if (difference[i] == -1) {
			if (recentOne == -1) {
				earlyNegativeBreak = true;
				break;
			} else {
				for (int j = i; j < recentOne; ++j) difference[j] = 1;
				difference[recentOne] = 0;
				recentOne = i;
			}
		}
	}
	if (earlyNegativeBreak) {
		answer(false);
	}
//	for (int i = diffLen - 1; i >= 0; --i) printf("%lld", difference[i]);
//	printf("\n");
//	fflush(stdout);
	reverse(begin(difference), end(difference)); // cast from little endian to big endian
	vector<ll> flows(n);
	flows[n-1] = tryDivide(difference, n);
	// flows[n-1] = (A + 2B + 4C + 8D + 16E) / 31
	// flows[n-2] = (E + 2A + 4B + 8C + 16D) / 31
	// 2a - b = A etc etc
	for (int i = n - 2; i >= 0; --i) flows[i] = 2*flows[i+1] - (before[i + 1] - after[i + 1]);
//	for (int i = 0; i < n; ++i) printf("%d flow %lld\n", i, flows[i]);
	for (int i = 0; i < n; ++i) if (flows[i] < 0) answer(false);
	answer(true);
	return 0;

}

Compilation message

remittance.cpp: In function 'std::vector<long long int> canonBinary(std::vector<long long int>&)':
remittance.cpp:12:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i + 1 < ans.size(); ++i) {
                  ~~~~~~^~~~~~~~~~~~
remittance.cpp: In function 'll tryDivide(std::vector<long long int>, ll)':
remittance.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (curRem.size() < n || (curRem.size() == n && curRemDigitSum < n)) {
       ~~~~~~~~~~~~~~^~~
remittance.cpp:38:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (curRem.size() < n || (curRem.size() == n && curRemDigitSum < n)) {
                             ~~~~~~~~~~~~~~^~~~
remittance.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (curRem.size() == n) {
        ~~~~~~~~~~~~~~^~~~
remittance.cpp: In function 'int main()':
remittance.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
remittance.cpp:90:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < n; ++i) scanf("%lld %lld", &before[i], &after[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 4 ms 256 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 256 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 5 ms 256 KB Output is correct
20 Incorrect 5 ms 384 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 4 ms 256 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 256 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 5 ms 256 KB Output is correct
20 Incorrect 5 ms 384 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 4 ms 256 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 256 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 5 ms 256 KB Output is correct
20 Incorrect 5 ms 384 KB Output isn't correct
21 Halted 0 ms 0 KB -