Submission #223584

#TimeUsernameProblemLanguageResultExecution timeMemory
223584spacewalkerRemittance (JOI19_remittance)C++14
100 / 100
544 ms114908 KiB
#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)

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]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...