oj.uz

Submission #44792

# Submission time Handle Problem Language Result Execution time Memory
44792 2018-04-06T13:40:43 Z model_code DEL13 (info1cup18_del13) C++17
100 / 100
 17 ms 2172 KB 
#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 ())
    {
        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

del13.cpp: In function 'int main()':
del13.cpp:81: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
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 11 ms 488 KB Output is correct
4 Correct 10 ms 488 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 612 KB Output is correct
2 Correct 3 ms 612 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 11 ms 488 KB Output is correct
4 Correct 10 ms 488 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 612 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 11 ms 488 KB Output is correct
4 Correct 10 ms 488 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 12 ms 884 KB Output is correct
9 Correct 11 ms 1028 KB Output is correct
10 Correct 11 ms 1172 KB Output is correct
11 Correct 17 ms 2172 KB Output is correct