oj.uz

Submission #494753

# Submission time Handle Problem Language Result Execution time Memory
494753 2021-12-16T05:30:02 Z syl123456 DEL13 (info1cup18_del13) C++17
100 / 100
 12 ms 1124 KB 
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wparentheses"
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define random random_device rd; mt19937 rng(rd())
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
    if (_split)
        cerr << ", ";
    cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
    cerr << '[';
    for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
    cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "Line(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << ']' << endl
#define debuga(i) cerr << "Line(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name()))
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int a[m + 1];
        for (int i = 0; i < m; ++i)
            cin >> a[i], --a[i];
        a[m] = n;
        if (n == m) {
            cout << "0\n\n";
            continue;
        }
        if (!m || n - m & 1) {
            cout << "-1\n";
            continue;
        }
        ++m;
        bool is[m], is2[m], fail = false;
        is[0] = a[0] == 0;
        is2[0] = !is[0] && ~a[0] & 1;
        for (int i = 1; i < m; ++i) {
            int x = a[i] - 1 - a[i - 1];
            is[i] = is2[i] = false;
            if (!is[i - 1] && !is2[i - 1]) {
                if (!x) {
                    fail = true;
                    break;
                }
                if (x & 1)
                    is[i] = true;
                if (x > 1 && x & 1)
                    is2[i] = true;
            }
            if (is[i - 1]) {
                if (!x)
                    is[i] = true;
                else if (~x & 1)
                    is2[i] = true;
            }
            if (is2[i - 1]) {
                if (x && ~x & 1)
                    is[i] = true;
                if (x > 2 && ~x & 1)
                    is2[i] = true;
            }
            if (!is[i - 1] && is2[i - 1]) {
                if (x < 2) {
                    fail = true;
                    break;
                }
            }
        }
        if (fail || !is[m - 1]) {
            cout << "-1\n";
            continue;
        }
        cout << (n - m + 1 >> 1) << '\n';
        int cnt[m];
        cnt[m - 1] = 0;
        for (int i = m - 1; i; --i) {
            int x = a[i] - 1 - a[i - 1];
            if (!cnt[i]) {
                if (!x)
                    cnt[i - 1] = 0;
                else
                    cnt[i - 1] = x & 1 ? 1 : 2;
            }
            else {
                x -= cnt[i];
                if (is[i - 1])
                    cnt[i - 1] = 0;
                else
                    cnt[i - 1] = x & 1 ? 1 : 2;
            }
        }
        for (int i = 0; i < m; ++i) {
            int x = i ? a[i - 1] + 3 : 2;
            int tmp = a[i] - 1 - (i ? a[i - 1] : -1);
            tmp -= cnt[i] + (i ? cnt[i - 1] : 0);
            for (int j = 0; j < tmp >> 1; ++j)
                cout << x << ' ', x += 2;
        }
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < cnt[i]; ++j)
                cout << a[i] + 1 << ' ';
        cout << '\n';
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 5 ms 348 KB Output is correct
4 Correct 3 ms 332 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 460 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 5 ms 348 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 5 ms 348 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 6 ms 400 KB Output is correct
9 Correct 6 ms 576 KB Output is correct
10 Correct 6 ms 564 KB Output is correct
11 Correct 12 ms 1124 KB Output is correct