Submission #681651

#	Time	Username	Problem	Language	Result	Execution time	Memory
681651		vovik	DEL13 (info1cup18_del13)	C++17	40 / 100	22 ms	6548 KiB

del13

//I wrote this code 4 u today
#include <bits/stdc++.h>

template<class t> using vc = std::vector<t>;

#define nd node*
#define pnd pair<nd, nd>

using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vc<pll> vpll;
typedef vc<vll> vvll;
typedef vc<vpll> vvpll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;

int main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t;
    cin >> t;
    for (int n, q; t-- && cin >> n >> q;) {
        vc<int> a(q);
        for (auto &i: a) cin >> i;
        a.insert(a.begin(), 0), a.push_back(n + 1);
        vc<vc<int>> p(n + 2, vc<int>(3, -1));
        p[0][0] = -2;
        for (int i = 0; i <= q; ++i) {
            for (int j = 0; j <= 2; ++j) {
                int l = a[i + 1] - a[i] - 1;
                if (p[i][j] + 1 && l >= j) {
                    if ((l - j) & 1 ^ 1) {
                        if (!l || j) p[i + 1][0] = j;
                        if (l - j) p[i + 1][2] = j;
                    } else p[i + 1][1] = j;
                }
            }
        }
        if (!(p[q + 1][0] + 1)) {
            cout << "-1\n";
            continue;
        }
        vc<int> ans;
        for (int i = q + 1, j = 0; --i; j = p[i + 1][j]) {
            for (int k = a[i + 1] - a[i] - 1 - j - p[i + 1][j]; k; k -= 2) {
                ans.push_back((a[i] + a[i + 1]) / 2);
            }
        }
        for (int i = q + 1, j = 0; i--; j = p[i + 1][j]) for (int k = j + 1; --k;) ans.push_back(a[i + 1]);
        cout << ans.size() << '\n';
        for (auto i: ans) cout << i << ' ';
        cout << '\n';
    }
}

Compilation message (stderr)

del13.cpp: In function 'int main()':
del13.cpp:57:33: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   57 |                     if ((l - j) & 1 ^ 1) {
      |                         ~~~~~~~~^~~

• Subtask 1: 6 / 15
• Subtask 2: 6 / 15
• Subtask 3: 6 / 15
• Subtask 4: 10 / 25
• Subtask 5: 12 / 30