oj.uz

Submission #197153

# Submission time Handle Problem Language Result Execution time Memory
197153 2020-01-19T10:11:57 Z Pankin DEL13 (info1cup18_del13) C++14
100 / 100
 66 ms 7652 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first.first
#define sc first.second
#define tr second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define pii pair<int, int>
#define tri pair< pair<int, int>, int >
#define mt(x, y, z) make_pair(make_pair(x, y), z)

const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;
using namespace __gnu_pbds;

bool valid(int x, int y, int n, int m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

mt19937 rng(1999999973);

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

signed main() {
    //fast_io;

    //getfiles;

    int tests;
    cin >> tests;
    while(tests--) {
        int n, q;
        cin >> n >> q;
        if (q == 0) {
            cout << -1 << endl;
            continue;
        }
        vector<int> p(q, 0), block(q + 2, 0);
        for (int i = 0; i < q; i++)
            cin >> p[i];
        block[0] = p[0] - 1;
        for (int i = 1; i < q; i++) {
            block[i] = p[i] - p[i - 1] - 1;
        }
        block[q] = n - p[q - 1];
        p.pb(n + 1);

        vector< vector< vector<tri> > > dp(q + 1);
        for (int i = 0; i <= q; i++) {
            dp[i].resize(block[i] + 1, vector<tri>(2, mt(-1, -1, -1)));
        }

        dp[0][block[0]][0] = mt(INF, INF, 0);
        for (int i = 0; i <= q; i++) {
            for (int j = block[i]; j >= 0; j--) {
                for (int k = 0; k < 2; k++) {
                    if (dp[i][j][k] == mt(-1, -1, -1))
                        continue;
                    if (j > 2)
                        dp[i][j - 2][k] = mt(i, j, k);
                    if (j == 2 && k == 1)
                        dp[i][j - 2][k] = mt(i, j, k);
                    if (i != q && j <= block[i + 1])
                        dp[i + 1][block[i + 1] - j][j != 0] = mt(i, j, k);
                }
            }
        }

        if (dp[q][0][0] == mt(-1, -1, -1) && dp[q][0][1] == mt(-1, -1, -1)) {
            cout << -1 << endl;
            continue;
        }
        cout << (n - q) / 2 << endl;

        tri cur;
        if (dp[q][0][0] != mt(-1, -1, -1))
            cur = mt(q, 0, 0);
        else
            cur = mt(q, 0, 1);

        tri init = mt(0, block[0], 0);
        vector<int> ans2;
        while(cur != init) {
            if (dp[cur.fs][cur.sc][cur.tr] == mt(cur.fs, cur.sc + 2, cur.tr)) {
                cout << p[cur.fs] - 1 - (block[cur.fs] - 1) / 2 << " ";
            }
            else {
                for (int i = 0; i < block[cur.fs] - cur.sc; i++)
                    ans2.pb(p[cur.fs - 1]);
            }
            cur = dp[cur.fs][cur.sc][cur.tr];
        }
        for (int i = 0; i < ans2.size(); i++)
            cout << ans2[i] << " ";
        if ((n - q) / 2 != 0)
            cout << endl;

    }

    return 0;
}

/*
1
15 5
1 2 3 6 10

111001000100000

*/

Compilation message

del13.cpp: In function 'int main()':
del13.cpp:113:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < ans2.size(); i++)
                         ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 23 ms 376 KB Output is correct
4 Correct 24 ms 380 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 756 KB Output is correct
2 Correct 22 ms 4984 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 23 ms 376 KB Output is correct
4 Correct 24 ms 380 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 23 ms 376 KB Output is correct
4 Correct 24 ms 380 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 50 ms 5492 KB Output is correct
9 Correct 57 ms 5584 KB Output is correct
10 Correct 56 ms 5496 KB Output is correct
11 Correct 66 ms 7652 KB Output is correct