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;
        cin >> n;
        map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            mp[tmp]++;
        }
        if (mp.size() == 1) cout << "YES" << endl;
        else if (mp.size() > 2) cout << "NO" << endl;
        else {
            cout << (abs(mp.begin()->second - mp.rbegin()->second) <= 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

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m;
        cin >> n >> m;
        string str1, str2;
        str1.reserve(n);
        str2.reserve(m);
        cin >> str1 >> str2;
        // check str 1
        bool f[2] = {false, false};
        for (int i = 1; i < n; ++i) if (str1[i] == str1[i - 1]) f[str1[i] - '0'] = true;
        if (f[0] && f[1]) {
            cout << "NO" << endl;
            continue;
        }
        if (!f[0] && !f[1]) {
            cout << "YES" << endl;
            continue;
        }
        // check str 2
        bool flag = true;
        for (int i = 1; i < m; ++i) if (str2[i] == str2[i - 1]) flag = false;
        if (!flag) {
            cout << "NO" << endl;
            continue;
        }
        if (f[str2[0] - '0']) {
            cout << "NO" << endl;
            continue;
        }
        if (f[str2[m - 1] - '0']) {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << 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

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        string str;
        str.reserve(n);
        cin >> str;
        if (n % 2) {
            cout << -1 << endl;
            continue;
        }
        list<char> l;
        for (auto &item : str) l.push_back(item);
        int lp = 0, rp = n;
        auto li = l.begin(), ri = l.end();
        --ri;
        bool flag = true;
        vector<int> ans;
        while (li != ri && lp < rp) {
            if (*li != *ri) {
                ++li;
                --ri;
                ++lp;
                --rp;
                continue;
            }
            if (*li == '0') {
                ans.push_back(rp);
                l.insert(++ri, '0');
                l.insert(ri, '1');
                --ri;
                rp += 2;
            } else if (*ri == '1') {
                ans.push_back(lp);
                l.insert(li, '1');
                --li;
                l.insert(li, '0');
                --li;
                rp += 2;
            }
            if (ans.size() > 300) {
                flag = false;
                break;
            }
        }
        if (!flag) {
            cout << -1 << endl;
        } else {
            cout << ans.size() << endl;
            for (int i = 0; i < ans.size(); ++i) cout << ans[i] << " \n"[i == ans.size() - 1];
        }
    }
}

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

#define int long long
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, c;
        cin >> n >> c;
        vector<pair<int, int>> data(n);
        for (auto&item: data) cin >> item.first;
        for (int i = 0; i < n; ++i) data[i].second = i + 1;
        int tot = data[0].first;
        sort(data.begin(), data.end(), [&](const pair<int, int>&lhs, const pair<int, int>&rhs) {
            return lhs.first - lhs.second * c > rhs.first - rhs.second * c;
        });
        bool flag = true;
        for (auto&item: data) {
            if (item.second == 1) continue;
            if (tot + item.first >= item.second * c) tot += item.first;
            else flag = false;
        }
        cout << (flag ? "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

#define int long long
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<vector<int>> start(n + 1), end(n + 1);
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            start[u].push_back(i);
            end[v].push_back(i);
        }
        set<int> s;
        map<pair<int, int>, int> ans1;
        map<int, int> ans2;
        int ans3 = 0;
        for (int i = 1; i <= n; ++i) {
            for (auto&item: start[i]) s.insert(item);
            if (s.empty())
                ans3++;
            else if (s.size() == 1)
                ans2[*s.begin()]++;
            else if (s.size() == 2)
                ans1[{*s.begin(), *s.rbegin()}]++;
            for (auto&item: end[i]) s.erase(item);
        }
        int res = ans3;
        for (auto&item: ans1) {
            int tmp = item.second + ans3;
            auto l = ans2.find(item.first.first), r = ans2.find(item.first.second);
            if (l != ans2.end()) tmp += l->second;
            if (r != ans2.end()) tmp += r->second;
            res = max(res, tmp);
        }
        vector<int> ans2v;
        ans2v.reserve(ans2.size());
        for (auto&item: ans2) ans2v.push_back(item.second);
        sort(ans2v.begin(), ans2v.end(), greater<>());
        if (ans2v.size() == 1) res = max(res, ans2v[0] + ans3);
        else if (ans2v.size() > 1) res = max(res, ans2v[0] + ans2v[1] + ans3);
        cout << res << endl;
    }
}