1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, tmp;
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> tmp;
        if (n % 2) {
            cout << 4 << endl;
            cout << 1 << ' ' << n << endl;
            cout << 1 << ' ' << n - 1 << endl;
            cout << n - 1 << ' ' << n << endl;
            cout << n - 1 << ' ' << n << endl;
        } else {
            cout << 2 << endl;
            cout << 1 << ' ' << n << endl;
            cout << 1 << ' ' << n << endl;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#define int long long
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k, a, b;
        cin >> n >> k >> a >> b;
        vector<pair<int, int>> data(n);
        for (auto &item: data) cin >> item.first >> item.second;
        auto dist = [&](int l, int r) {
            return abs(data[l].first - data[r].first) + abs(data[l].second - data[r].second);
        };
        int ans = dist(a - 1, b - 1);
        int ak = INT_MAX * 2LL, bk = INT_MAX * 2LL;
        for (int i = 0; i < k; ++i) {
            ak = min(ak, dist(i, a - 1));
            bk = min(bk, dist(i, b - 1));
        }
        cout << min(ans, ak + bk) << endl;
    }
}

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

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m;
        cin >> n >> m;
        if (m == 1) {
            cout << 0 << endl;
        } else if (n >= m - 1) {
            cout << m << endl;
        } else {
            cout << n + 1 << endl;
        }
        for (int i = 0; i < min(n, m - 1); ++i) {
            for (int j = 0; j < m; ++j) {
                cout << (j - i - 1 + m) % m << ' ';
            }
            cout << endl;
        }
        for (int i = min(n, m - 1); i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cout << (j + 1) % m << ' ';
            }
            cout << endl;
        }
    }
}

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

#define int long long
void solve() {
    vector<int> mi(40);
    for (int i = 0; i < 40; ++i) mi[i] = 1LL << i;
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto &item: data) cin >> item;
        int sum = 0;
        for (auto &item: data) sum += item;
        if (sum % n != 0) {
            cout << "No" << endl;
            continue;
        }
        sum /= n;
        auto lowBit = [](int x) { return x & -x; };
        vector<int> p[2];
        p[0].reserve(n);
        p[1].reserve(n);
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            int diff = data[i] - sum;
            if (diff == 0) continue;
            int l = diff > 0 ? 0 : 1, r = 1 ^ l;
            diff = abs(diff);
            int b = *upper_bound(mi.begin(), mi.end(), diff);
            int s = b - diff;
            if (*lower_bound(mi.begin(), mi.end(), s) != s) {
                flag = false;
                break;
            }
            p[l].push_back(b);
            p[r].push_back(s);
        }
        sort(p[0].begin(), p[0].end());
        sort(p[1].begin(), p[1].end());
        cout << (flag && p[0] == p[1] ? "YES" : "NO") << endl;
    }
}

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

#define int long long
void solve() {
    vector<int> mi(40);
    for (int i = 0; i < 40; ++i) mi[i] = 1LL << i;
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto &item: data) cin >> item;
        int sum = 0;
        for (auto &item: data) sum += item;
        if (sum % n != 0) {
            cout << "No" << endl;
            continue;
        }
        sum /= n;
        struct cmp {
            bool operator()(const int &lhs, const int &rhs) const {
                return abs(lhs) < abs(rhs);
            }
        };
        priority_queue<int, vector<int>, cmp> depart;
        map<int, int, greater<>> pos, neg;
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            int dif = data[i] - sum;
            if (dif == 0) continue;
            if (abs(dif) == *lower_bound(mi.begin(), mi.end(), abs(dif))) {
                // good gay
                (dif > 0 ? pos : neg)[abs(dif)]++;
            } else {
                // bad gay
                int b = *upper_bound(mi.begin(), mi.end(), abs(dif));
                b *= dif > 0 ? 1 : -1;
                int s = dif - b;
                if (abs(s) != *lower_bound(mi.begin(), mi.end(), abs(s))) {
                    flag = false;
                    break;
                }
                depart.push(b);
                depart.push(s);
            }
        }
        if (!flag) {
            cout << "NO" << endl;
            continue;
        }
        while (!depart.empty() || !pos.empty() || !neg.empty()) {
            if (depart.empty()) {
                auto posIter = pos.begin(), negIter = neg.begin();
                if (posIter->first == negIter->first) {
                    int tmp = min(posIter->second, negIter->second);
                    posIter->second -= tmp;
                    negIter->second -= tmp;
                    if (posIter->second == 0) pos.erase(posIter);
                    if (negIter->second == 0) neg.erase(negIter);
                    continue;
                }
                auto &iter = posIter->first > negIter->first ? posIter : negIter;
                auto mx = posIter->first > negIter->first ? 1 : -1;
                auto &u = posIter->first > negIter->first ? pos : neg;
                auto &v = posIter->first > negIter->first ? neg : pos;
                auto tIter = v.find(iter->first / 2);
                if (tIter == v.end()) {
                    flag = false;
                    break;
                }
                int tmp = min(iter->second, tIter->second);
                for (int i = 0; i < tmp; ++i) depart.push(mx * iter->first / 2);
                iter->second -= tmp;
                tIter->second -= tmp;
                if (iter->second == 0) u.erase(iter);
                if (tIter->second == 0) v.erase(tIter);
            }
            while (!pos.empty() || !neg.empty()) {
                auto posIter = pos.begin();
                auto negIter = neg.begin();
                bool posWin = negIter == neg.end() || (posIter != pos.end() && posIter->first > negIter->first);
                auto &maxIter = posWin ? posIter : negIter;
                auto &maxLink = posWin ? pos : neg;
                auto mx = posWin ? 1 : -1;
                if (maxIter->first > abs(depart.top())) {
                    for (int i = 0; i < maxIter->second; ++i) depart.push(mx * maxIter->first);
                    maxLink.erase(maxIter);
                } else {
                    break;
                }
            }
            int cnt[2] = {depart.top() < 0, depart.top() > 0};
            int cur = abs(depart.top());
            depart.pop();
            while (!depart.empty() && abs(depart.top()) == cur) {
                cnt[0] += depart.top() < 0;
                cnt[1] += depart.top() > 0;
                depart.pop();
            }
            // receives from not good gay
            int tmp = min(cnt[0], cnt[1]);
            cnt[0] -= tmp;
            cnt[1] -= tmp;
            if (cnt[0] == 0 && cnt[1] == 0) continue;
            int left = cnt[0] > 0 ? 0 : 1;
            auto &link = cnt[0] > 0 ? pos : neg;
            int mx = cnt[0] > 0 ? -1 : 1;
            // find in pos which is equals to this gay
            auto iter = link.find(cur);
            if (iter != link.end()) {
                tmp = min(cnt[left], iter->second);
                iter->second -= tmp;
                cnt[left] -= tmp;
                if (iter->second == 0) link.erase(iter);
            }
            if (cnt[left] == 0) continue;
            // not enough, find in pos which is half of this gay
            iter = link.find(cur / 2);
            if (iter != link.end()) {
                tmp = min(cnt[left], iter->second);
                for (int i = 0; i < tmp; ++i) depart.push(mx * cur / 2);
                iter->second -= tmp;
                cnt[left] -= tmp;
                if (iter->second == 0) link.erase(iter);
            }
            if (cnt[left] != 0) {
                flag = false;
                break;
            }
        }
        cout << (flag ? "YES" : "NO") << endl;
    }
}