Submission #97230

#	Time	Username	Problem	Language	Result	Execution time	Memory
97230		alextodoran	DEL13 (info1cup18_del13)	C++14	0 / 100	19 ms	2424 KiB

del13

#include <bits/stdc++.h>

#define NM 100002

using namespace std;

int t;

int n, q;

int p[NM];
int v[NM];

deque <int> op;

int dp[NM][3], dp1[NM][3];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n >> q;
        for(int i = 1; i <= q; i++)
            cin >> p[i];
        q++;
        p[q] = n + 1;
        int sum = 0;
        for(int i = 1; i <= q; i++)
        {
            v[i] = p[i] - p[i - 1] - 1;
            sum += v[i];
        }
        for(int i = 0; i < q; i++)
            for(int j = 0; j <= 2; j++)
                dp[i][j] = 0;
        dp[0][0] = 1;
        for(int i = 0; i < q - 1; i++)
            for(int j = 0; j <= 2; j++)
            {
                if(dp[i][j] == 0)
                    continue;
                if((j > 0 || v[i + 1] == 0) && (v[i + 1] - j) % 2 == 0 && v[i + 1] >= j)
                {
                    dp[i + 1][0] = 1;
                    dp1[i + 1][0] = j;
                }
                if(v[i + 1] >= j + 1 && (v[i + 1] - (j + 1)) % 2 == 0 && v[i + 2] >= 1)
                {
                    dp[i + 1][1] = 1;
                    dp1[i + 1][1] = j;
                }
                if(v[i + 1] >= j + 2 && (v[i + 1] - (j + 2)) % 2 == 0 && v[i + 2] >= 2)
                {
                    dp[i + 1][2] = 1;
                    dp1[i + 1][2] = j;
                }
            }
        if(!(dp[q - 1][1] || dp[q - 1][2] || dp[q - 1][0]))
        {
            cout << "-1\n";
            continue;
        }
        int cnt;
        if(dp[q - 1][0])
            cnt = 0;
        else if(dp[q - 1][1])
            cnt = 1;
        else
            cnt = 2;
        cout << sum / 2 << "\n";
        for(int i = q - 1; i >= 1; i--)
        {
            int val = cnt + dp1[i][cnt];
            for(int j = 1; j <= (v[i] - val) / 2; j++)
                cout << p[i - 1] + (v[i] + 1) / 2 << " ";
            for(int j = 1; j <= cnt; j++)
                cout << p[i] << " ";
            cnt = dp1[i][cnt];
        }
        cout << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30