CompetitiveProgramming/codeforces/657/B.cpp at master · phonglnDEV/CompetitiveProgramming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR(A,n)  { cout << #A << " = "; FOR(_,1,n) cout << A[_] << ' '; cout << endl; }
#define PR0(A,n) { cout << #A << " = "; REP(_,n) cout << A[_] << ' '; cout << endl; }

#define sqr(x) ((x) * (x))
#define ll long long
#define __builtin_popcount __builtin_popcountll
#define SZ(x) ((int) (x).size())
using namespace std;

const int MN = 200111;
const int INF = 1000111000111000111LL;

int a[MN], n, k;
pair<int,int> l[MN], r[MN], b[MN];

#undef int
int main() {
#define int long long
    ios :: sync_with_stdio(0); cin.tie(0);
    cout << (fixed) << setprecision(9);
    while (scanf("%lld%lld", &n, &k) == 2) {
        FOR(i,0,n) scanf("%lld", &a[i]);

        memset(l, 0, sizeof l);
        memset(r, 0, sizeof r);

        // go from left
        FOR(i,0,n-1) {
            // use a[i] --> b[i]
            if (i == 0) {
                // a[0] = -2 * b[0]
                if (a[i] % 2 != 0) {
                    break;
                }
                else {
                    b[i].first = 1;
                    b[i].second = a[i] / -2;
                }
            }
            else {
                // a[i] = b[i-1] - 2 * b[i]
                if ((a[i] - b[i-1].second) % 2) {
                    break;
                }
                else {
                    b[i].first = 1;
                    b[i].second = (a[i] - b[i-1].second) / -2;
                }
            }
            if (llabs(b[i].second) > INF) {
                b[i].first = 0;
                break;
            }
        }
//        FOR(i,0,n-1) cout << b[i].first << ' ' << b[i].second << endl;
        FOR(i,0,n-1) l[i] = b[i];

        // go from right
        FORD(i,n,1) {
            if (i == n) {
                b[i-1].first = 1;
                b[i-1].second = a[i];
            }
            else {
                // a[i] = b[i-1] - 2*b[i]
                b[i-1].first = 1;
                b[i-1].second = a[i] + 2*b[i].second;
            }
            if (llabs(b[i].second) > INF) {
                b[i].first = 0;
                break;
            }
        }

//        cout << endl;
//        FOR(i,0,n-1) cout << b[i].first << ' ' << b[i].second << endl;
        FOR(i,0,n-1) r[i] = b[i];

        int res = 0;
        FOR(i,0,n) {
            // if we change a[i]
//            DEBUG(i);
            if (i == 0) {
                int newa0 = -2 * r[0].second;
//                DEBUG(newa0);
                if (r[0].first && llabs(newa0) <= k && newa0 != a[0]) ++res;
            }
            else if (i == n) {
                if (l[n-1].first) {
                    int newa = l[n-1].second;
//                    DEBUG(newa);
                    if (llabs(newa) <= k && newa && newa != a[n]) ++res;
                }
            }
            else {
                if (l[i-1].first && r[i].first) {
                    ll b0 = l[i-1].second;
                    ll b1 = r[i].second;
                    ll newa = b0 - 2 * b1;
//                    DEBUG(newa);
                    if (llabs(newa) <= k && newa != a[i]) ++res;
                }
            }
        }
        cout << res << endl;
//        cout << "----" << endl;
    }
}