# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
223584 | spacewalker | Remittance (JOI19_remittance) | C++14 | 544 ms | 114908 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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]);
ll sanity = 0;
for (int i = 0; i < n; ++i) if (before[i] != after[i]) ++sanity;
if (sanity == 0) answer(true);
sanity = 0;
for (int x : after) sanity += x;
if (sanity == 0) answer(false);
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |