#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<ll> a(n), b(n);
vector<ll> lul(n + 33);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
lul[i] = a[i] - b[i];
}
// t[n - 1] = sigma(2^i * (a[i] - b[i])) / (2^n - 1)
for (int i = 0; i + 1 < lul.size(); i++) {
lul[i + 1] += lul[i] / 2;
lul[i] %= 2;
if (lul[i] < 0) {
lul[i] += 2;
lul[i + 1]--;
}
}
if (find(lul.begin(), lul.end(), -1) != lul.end()) {
cout << "No\n";
return 0;
}
reverse(lul.begin(), lul.end());
int pos = find(lul.begin(), lul.end(), 1) - lul.begin();
for (int i = pos; i < pos + n && pos + n <= lul.size(); i++) {
if (!lul[i]) {
cout << "No\n";
return 0;
}
}
ll kek = 1;
for (int i = pos + n; i < lul.size(); i++) {
kek = kek * 2 + lul[i];
}
if (pos == lul.size()) {
kek = 0;
}
ll heh = 0;
for (int i = max(0, n - 32); i + 1 < n; i++) {
heh += a[i];
heh /= 2;
}
if (heh + a[n - 1] < kek * 2) {
cout << kek << "No\n";
return 0;
}
a[n - 1] -= 2 * kek;
a[0] += kek;
for (int i = 0; i < n - 1; i++) {
if (a[i] < b[i] || (a[i] - b[i]) % 2) {
cout << "No\n";
return 0;
}
ll mem = (a[i] - b[i]) / 2;
a[i] -= mem * 2;
a[i + 1] += mem;
}
if (a[n - 1] != b[n - 1]) {
cout << "No\n";
} else {
cout << "Yes\n";
}
return 0;
}
Compilation message
remittance.cpp: In function 'int main()':
remittance.cpp:23:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i + 1 < lul.size(); i++) {
~~~~~~^~~~~~~~~~~~
remittance.cpp:37:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = pos; i < pos + n && pos + n <= lul.size(); i++) {
~~~~~~~~^~~~~~~~~~~~~
remittance.cpp:44:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = pos + n; i < lul.size(); i++) {
~~^~~~~~~~~~~~
remittance.cpp:47:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos == lul.size()) {
~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
4 ms |
384 KB |
Output is correct |
| 14 |
Correct |
4 ms |
384 KB |
Output is correct |
| 15 |
Correct |
4 ms |
384 KB |
Output is correct |
| 16 |
Correct |
4 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
4 ms |
384 KB |
Output is correct |
| 19 |
Correct |
4 ms |
384 KB |
Output is correct |
| 20 |
Correct |
4 ms |
384 KB |
Output is correct |
| 21 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
4 ms |
384 KB |
Output is correct |
| 14 |
Correct |
4 ms |
384 KB |
Output is correct |
| 15 |
Correct |
4 ms |
384 KB |
Output is correct |
| 16 |
Correct |
4 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
4 ms |
384 KB |
Output is correct |
| 19 |
Correct |
4 ms |
384 KB |
Output is correct |
| 20 |
Correct |
4 ms |
384 KB |
Output is correct |
| 21 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
4 ms |
384 KB |
Output is correct |
| 14 |
Correct |
4 ms |
384 KB |
Output is correct |
| 15 |
Correct |
4 ms |
384 KB |
Output is correct |
| 16 |
Correct |
4 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
4 ms |
384 KB |
Output is correct |
| 19 |
Correct |
4 ms |
384 KB |
Output is correct |
| 20 |
Correct |
4 ms |
384 KB |
Output is correct |
| 21 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
