oj.uz

Submission #564203

# Submission time Handle Problem Language Result Execution time Memory
564203 2022-05-18T17:53:01 Z 4fecta Remittance (JOI19_remittance) C++17
0 / 100
 343 ms 16204 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 1000005;

int n;
pii a[MN * 2];

int fpow(int b, int p, int mod) {
    if (!p) return 1;
    int ret = fpow(b, p / 2, mod);
    if (p & 1) return ret * ret % mod * b % mod;
    return ret * ret % mod;
}

int32_t main() {
    boost();

    cin >> n;
    int suma = 0, sumb = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i].f >> a[i].s;
        suma += a[i].f * (1ll << i);
        sumb += a[i].s * (1ll << i);
    }
    int was = (1ll << n) - 1;
    int d = suma - sumb;
    if (d % was != 0) return 0 * printf("No\n");
    for (int i = 0; i < MN; i++) {
        if (a[i].s > a[i].f) {
            int d = a[i].s - a[i].f;
            a[i].s -= d;
            a[i + n].s += d;
        }
        int d = a[i].f - a[i].s;
        int tk = min(a[i].f / 2, (d + 1) / 2);
        a[i].f -= tk * 2;
        a[i + 1].f += tk;
        if (a[i].s > a[i].f) {
            int d = a[i].s - a[i].f;
            a[i].s -= d;
            a[i + n].s += d;
        }
        if (a[i].f > a[i].s) {
            int d = a[i].f - a[i].s;
            a[i].f -= d;
            a[i + n].f += d;
        }
    }
    int sum = 0;
    for (int i = 0; i < MN * 2; i++) {
        assert(a[i].f >= 0 && a[i].s >= 0);
        if (a[i].f < a[i].s) return 0 * printf("No\n");
        sum += fpow(2, i, was) * (a[i].f - a[i].s) % was;
    }
    if (sum % was == 0) printf("Yes\n");
    else printf("No\n");

    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 326 ms 15976 KB Output is correct
3 Correct 325 ms 15976 KB Output is correct
4 Correct 326 ms 15980 KB Output is correct
5 Correct 319 ms 15984 KB Output is correct
6 Correct 341 ms 16000 KB Output is correct
7 Correct 332 ms 15964 KB Output is correct
8 Correct 329 ms 15984 KB Output is correct
9 Correct 324 ms 15960 KB Output is correct
10 Correct 343 ms 16204 KB Output is correct
11 Correct 340 ms 15992 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 162 ms 15968 KB Output is correct
17 Correct 164 ms 15968 KB Output is correct
18 Correct 323 ms 15992 KB Output is correct
19 Correct 168 ms 16020 KB Output is correct
20 Incorrect 321 ms 16084 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 326 ms 15976 KB Output is correct
3 Correct 325 ms 15976 KB Output is correct
4 Correct 326 ms 15980 KB Output is correct
5 Correct 319 ms 15984 KB Output is correct
6 Correct 341 ms 16000 KB Output is correct
7 Correct 332 ms 15964 KB Output is correct
8 Correct 329 ms 15984 KB Output is correct
9 Correct 324 ms 15960 KB Output is correct
10 Correct 343 ms 16204 KB Output is correct
11 Correct 340 ms 15992 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 162 ms 15968 KB Output is correct
17 Correct 164 ms 15968 KB Output is correct
18 Correct 323 ms 15992 KB Output is correct
19 Correct 168 ms 16020 KB Output is correct
20 Incorrect 321 ms 16084 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 326 ms 15976 KB Output is correct
3 Correct 325 ms 15976 KB Output is correct
4 Correct 326 ms 15980 KB Output is correct
5 Correct 319 ms 15984 KB Output is correct
6 Correct 341 ms 16000 KB Output is correct
7 Correct 332 ms 15964 KB Output is correct
8 Correct 329 ms 15984 KB Output is correct
9 Correct 324 ms 15960 KB Output is correct
10 Correct 343 ms 16204 KB Output is correct
11 Correct 340 ms 15992 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 162 ms 15968 KB Output is correct
17 Correct 164 ms 15968 KB Output is correct
18 Correct 323 ms 15992 KB Output is correct
19 Correct 168 ms 16020 KB Output is correct
20 Incorrect 321 ms 16084 KB Output isn't correct
21 Halted 0 ms 0 KB -