Submission #197147

#	Time	Username	Problem	Language	Result	Execution time	Memory
197147		Pankin	DEL13 (info1cup18_del13)	C++14	40 / 100	10 ms	1524 KiB

del13

#include<bits/stdc++.h>

using namespace std;

int N, l[100009], lft[100009], rgt[100009], cnt[100009], how[100009][3];
bool dp[100009][3], ap[100009], aft[100009];
vector < int > ans;

bool isSolvable ()
{
    int nr = 0;
    for (int i=1; i<=N; i++)
        if (ap[i] == 0)
        {
            int j;
            for (j=i; j<=N; j++)
                if (ap[j])
                    break;
            j --;
            l[++nr] = j - i + 1, lft[nr] = i, rgt[nr] = j;
            aft[nr] = (j + 1 < N && ap[j + 1] == 1 && ap[j + 2] == 0);
            i = j;
        }
    ans.clear ();
    if (nr == 0) return 1;
    if (aft[1] == 0) return 0;
    for (int i=1; i<=nr; i++)
        for (int j=0; j<3; j++)
            dp[i][j] = 0;
    for (int i=1; i<=2; i++)
        dp[1][i] = (i <= l[1] && (l[1] - i) % 2 == 0);
    for (int i=1; i<nr; i++)
        for (int j=0; j<=2; j++)
            if (dp[i][j])
            {
                for (int k=0; k<=2; k++)
                {
                    if (k != 0 && aft[i + 1] == 0) continue;
                    if (j + k >= 1 && l[i + 1] >= j + k && (l[i + 1] - j - k) % 2 == 0)
                        dp[i + 1][k] = 1, how[i + 1][k] = j;
                }
            }
    if (dp[nr][0] == 0) return 0;
    int k = 0;
    for (int i=nr; i>=1; i--)
        cnt[i] = k, k = how[i][k];
    for (int i=1; i<=nr; i++)
    {
        int q = cnt[i] + cnt[i - 1];
        assert (q >= 1 && q <= l[i]);
        assert ((l[i] - q) % 2 == 0);
        if ((l[i] - q) / 2 > 0)
        {
            int pairs = (l[i] - q) / 2, x = rgt[i] - pairs;
            while (pairs --)
                ans.push_back (x);
        }
    }
    for (int i=1; i<nr; i++)
        while (cnt[i] --)
            ans.push_back (rgt[i] + 1), assert (rgt[i] + 1 == lft[i + 1] - 1);
    return 1;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

int tests, sumN = 0;
assert (scanf ("%d", &tests) == 1);
while (tests --)
{
    int currL = 0, x;
    assert (scanf ("%d %d", &N, &currL) == 2), sumN += N;
    for (int i=1; i<=N; i++) ap[i] = 0;
    while (currL --)
        assert (scanf ("%d", &x) == 1), ap[x] = 1;
    if (isSolvable ())
    {
        ans.clear();
        printf ("%d\n", ans.size ());
        for (auto it : ans)
            printf ("%d ", it);
        printf ("\n");
    }
    else printf ("-1\n");
}
assert (tests <= 2000);

return 0;
}

Compilation message (stderr)

del13.cpp: In function 'int main()':
del13.cpp:82:36: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
         printf ("%d\n", ans.size ());
                         ~~~~~~~~~~~^

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