oj.uz

Submission #681651

# Submission time Handle Problem Language Result Execution time Memory
681651 2023-01-13T14:21:51 Z vovik DEL13 (info1cup18_del13) C++17
40 / 100
 22 ms 6548 KB 
//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

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.0 / 15.0

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

Subtask #2
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is partially correct
2 Correct 1 ms 212 KB Output is partially correct
3 Correct 5 ms 340 KB Output is partially correct
4 Correct 6 ms 340 KB Output is partially correct

Subtask #3
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 724 KB Output is partially correct
2 Correct 10 ms 4824 KB Output is partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is partially correct
2 Correct 1 ms 212 KB Output is partially correct
3 Correct 5 ms 340 KB Output is partially correct
4 Correct 6 ms 340 KB Output is partially correct
5 Correct 1 ms 340 KB Output is partially correct
6 Correct 1 ms 340 KB Output is partially correct
7 Correct 1 ms 340 KB Output is partially correct

Subtask #5
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is partially correct
2 Correct 1 ms 212 KB Output is partially correct
3 Correct 5 ms 340 KB Output is partially correct
4 Correct 6 ms 340 KB Output is partially correct
5 Correct 1 ms 340 KB Output is partially correct
6 Correct 1 ms 340 KB Output is partially correct
7 Correct 1 ms 340 KB Output is partially correct
8 Correct 16 ms 5632 KB Output is partially correct
9 Correct 18 ms 5780 KB Output is partially correct
10 Correct 17 ms 5460 KB Output is partially correct
11 Correct 22 ms 6548 KB Output is partially correct