oj.uz

Submission #97235

# Submission time Handle Problem Language Result Execution time Memory
97235 2019-02-14T14:39:13 Z alextodoran DEL13 (info1cup18_del13) C++14
0 / 100
 24 ms 2168 KB 
#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 j = 1; j <= (v[q] - cnt) / 2; j++)
            cout << p[q - 1] + (v[q] + 1) / 2 << " ";
        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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 428 KB Output isn't correct
2 Incorrect 4 ms 384 KB Output isn't correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 428 KB Output isn't correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Incorrect 6 ms 384 KB Output isn't correct
4 Incorrect 5 ms 384 KB Output isn't correct

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 584 KB Output isn't correct
2 Incorrect 3 ms 512 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 428 KB Output isn't correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Incorrect 6 ms 384 KB Output isn't correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Correct 3 ms 384 KB Output is correct
6 Incorrect 3 ms 384 KB Output isn't correct
7 Incorrect 3 ms 256 KB Output isn't correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 428 KB Output isn't correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Incorrect 6 ms 384 KB Output isn't correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Correct 3 ms 384 KB Output is correct
6 Incorrect 3 ms 384 KB Output isn't correct
7 Incorrect 3 ms 256 KB Output isn't correct
8 Correct 12 ms 640 KB Output is correct
9 Correct 10 ms 1024 KB Output is correct
10 Correct 14 ms 1152 KB Output is correct
11 Correct 24 ms 2168 KB Output is correct