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

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, last, diff = INT_MAX;
        cin >> n;
        cin >> last;
        for (int i = 0; i < n - 1; ++i) {
            int tmp;
            cin >> tmp;
            diff = min(diff, tmp - last);
            last = tmp;
        }
        cout << max(0, (diff + 2) / 2) << 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

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k;
        cin >> n >> k;
        if (k >= n && k > 10) {
            cout << 0 << endl;
            continue;
        }
        int x[3] = {0, 1, 0}, y[3] = {0, 0, 1};
        for (int i = 2; i < k; ++i) {
            x[0] = x[1];
            x[1] = x[2];
            y[0] = y[1];
            y[1] = y[2];
            x[2] = x[0] + x[1];
            y[2] = y[0] + y[1];
        }
        int tx = x[2], ty = y[2], ans = 0;
        for (int i = 0; i < n; ++i) {
            if (tx * i > n) break;
            if ((n - tx * i) % ty == 0 && (n - tx * i) / ty >= i) ans++;
        }
        cout << ans << endl;
    }
}

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

#define int long long
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        int j = 0, x = 1;
        while (k--) {
            while (j < n && a[j] <= x + j) j++;
            x += j;
        }
        cout << x << 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

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto &item: data) cin >> item;
        vector<int> ans(n);
        vector<int> usePos;
        set<int> notUse;
        for (int i = 1; i <= n; ++i) notUse.insert(i);
        vector<pair<int, int>> sorted(n);
        for (int i = 0; i < n; ++i) sorted[i] = {data[i], i};
        sort(sorted.begin(), sorted.end(), greater<>());
        int cur = n, last = n;
        for (auto &item: sorted) {
            cur -= last - item.first;
            if (cur <= 0) break;
            ans[item.second] = cur;
            notUse.erase(cur);
            usePos.push_back(cur);
            --cur;
            last = item.first;
        }
        sort(usePos.begin(), usePos.end(), greater<>());
        sort(sorted.begin(), sorted.end());
        int i = 0;
        bool flag = true;
        for (auto iter = notUse.rbegin(); iter != notUse.rend(); ++iter) {
            int cnt = int(upper_bound(usePos.begin(), usePos.end(), *iter, greater<>()) - usePos.begin());
            if (cnt != sorted[i].first) {
                flag = false;
                break;
            }
            ans[sorted[i].second] = -*iter;
            i++;
        }
        if (!flag) {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        for (auto &item : ans) cout << item << ' ';
        cout << endl;
    }
}