Submission #916953

# Submission time Handle Problem Language Result Execution time Memory
916953 2024-01-26T20:31:32 Z andrei_iorgulescu DEL13 (info1cup18_del13) C++14
40 / 100
18 ms 19036 KB
#include <bits/stdc++.h>

using namespace std;

int n,q,p[100005];
vector<bool> dp[100005];///pot sa fac primele i a.i sa am las j in grupul de dupa?
vector<pair<int,int>> pre[100005];///daca dp[i][j] e adevarat, fac operatia op[i][j] si merg in starea pre[i][j]
vector<pair<int,int>> op[100005];
vector<int> sumsuf[100005];

bool orr(bool xx,bool yy)
{
    if (xx == true or yy == true)
        return true;
    return false;
}

void solveq1()
{
    if (n == 1)
    {
        cout << 0 << '\n' << '\n';
        return;
    }
    if (p[1] == 1 or p[1] == n)
    {
        cout << -1 << '\n';
        return;
    }
    int parl = p[1] - 1,parr = n - p[1];
    if (parl % 2 != parr % 2)
    {
        cout << -1 << '\n';
        return;
    }
    cout << (n - 1) / 2 << '\n';
    if (parl % 2 == 1)
    {
        int mijl = p[1] / 2;
        for (int i = 1; i < mijl; i++)
            cout << mijl << ' ';
        int dif = n - p[1];
        int mijr = n - dif / 2;
        for (int i = mijr + 1; i <= n; i++)
            cout << mijr << ' ';
        cout << p[1] << '\n';
    }
    else
    {
        int mijl = p[1] / 2;
        for (int i = 1; i < mijl; i++)
            cout << mijl << ' ';
        int dif = n - p[1];
        int mijr = n - (dif / 2 - 1);
        for (int i = mijr + 1; i <= n; i++)
            cout << mijr << ' ';
        cout << p[1] << ' ' << p[1] << '\n';
    }
}

void testcase()
{
    cin >> n >> q;
    for (int i = 1; i <= q; i++)
        cin >> p[i];
    if (q == 0)
    {
        if (n == 0)
        {
            cout << 0 << '\n' << '\n';
        }
        else
            cout << -1 << '\n';
        return;
    }
    if (q == 1)
    {
        solveq1();
        return;
    }
    p[q + 1] = n + 1;
    for (int i = 1; i <= q; i++)
    {
        dp[i].resize(p[i + 1] - p[i],false);
        pre[i].resize(p[i + 1] - p[i],{0,0});
        op[i].resize(p[i + 1] - p[i],{0,0});
        sumsuf[i].resize(p[i + 1] - p[i],0);
        for (int j = 0; j <= p[i + 1] - p[i] - 1; j++)
        {
            dp[i][j] = false;
            pre[i][j] = {0,0};
            op[i][j] = {0,0};
            sumsuf[i][j] = 0;
        }
    }
    for (int j = 0; j <= p[2] - p[1] - 1; j++)
    {
        ///raman j pe spatiu
        if (j == p[2] - p[1] - 1)
        {
            if (p[1] == 1)
                dp[1][j] = true;
            else
                dp[1][j] = false;
        }
        else
        {
            int nrop = p[2] - p[1] - 1 - j;
            if (nrop >= p[1] or (p[1] - 1 - nrop) % 2 != 0)
                dp[1][j] = false;
            else
                dp[1][j] = true;
        }
        //cout << (int)dp[1][j] << ' ';
    }
    for (int j = p[2] - p[1] - 1; j >= 0; j--)
    {
        sumsuf[1][j] = (int)dp[1][j];
        if (j + 2 <= p[2] - p[1] - 1)
            sumsuf[1][j] += sumsuf[1][j + 2];
    }
    //cout << '\n';
    for (int i = 2; i <= q; i++)
    {
        for (int j = 0; j <= p[i + 1] - p[i] - 1; j++)
        {
            int nrop = p[i + 1] - p[i] - 1 - j;
            ///vin din dp[i - 1][q], q >= nrop si q de aceeasi paritate cu nrop
            ///partea proasta e cand nrop = 0,q = p[i] - p[i - 1] - 1
            if (nrop != 0)
            {
                ///suma pe sufixul de la nrop
                if (nrop > p[i] - p[i - 1] - 1)
                    dp[i][j] = false;
                else
                {
                    int sm = sumsuf[i - 1][nrop];
                    if (sm > 0)
                        dp[i][j] = true;
                    else
                        dp[i][j] = false;
                }
                //for (int qq = nrop; qq <= p[i] - p[i - 1] - 1; qq += 2)
                  //  dp[i][j] = orr(dp[i - 1][qq],dp[i][j]);
            }
            else
            {
                ///suma pe sufixul de la nrop cu cazul particular
                if (nrop > p[i] - p[i - 1] - 1)
                    dp[i][j] = false;
                else
                {
                    int sm = sumsuf[i - 1][nrop];
                    if (sm == 0 or (sm == 1 and dp[i - 1][p[i] - p[i - 1] - 1] == true and p[i] - p[i - 1] - 1 != 0))
                        dp[i][j] = false;
                    else
                        dp[i][j] = true;
                }
                /*for (int qq = nrop; qq <= p[i] - p[i - 1] - 1; qq += 2)
                    if (qq != p[i] - p[i - 1] - 1 or p[i] - p[i - 1] - 1 == 0)
                        dp[i][j] = orr(dp[i - 1][qq],dp[i][j]);*/
            }
            //cout << (int)dp[i][j] << ' ';
        }
        for (int j = p[i + 1] - p[i] - 1; j >= 0; j--)
        {
            sumsuf[i][j] = (int)dp[i][j];
            if (j + 2 <= p[i + 1] - p[i] - 1)
                sumsuf[i][j] += sumsuf[i][j + 2];
        }
        //cout << '\n';
    }
    bool ans = false;
    for (int i = 0; i <= n - p[q]; i += 2)
    {
        if (i != n - p[q])
            ans = orr(ans,dp[q][i]);
        else if (n == p[q])
            ans = orr(ans,dp[q][i]);
    }
    if (ans == true)
        cout << 0 << '\n' << '\n';
    else
        cout << -1 << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin >> tc;
    while (tc--)
        testcase();
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is partially correct
2 Correct 4 ms 11352 KB Output is partially correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is partially correct
2 Correct 4 ms 11352 KB Output is partially correct
3 Correct 5 ms 11352 KB Output is partially correct
4 Correct 5 ms 11356 KB Output is partially correct
# Verdict Execution time Memory Grader output
1 Correct 7 ms 13916 KB Output is partially correct
2 Correct 8 ms 14940 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is partially correct
2 Correct 4 ms 11352 KB Output is partially correct
3 Correct 5 ms 11352 KB Output is partially correct
4 Correct 5 ms 11356 KB Output is partially correct
5 Correct 3 ms 11356 KB Output is partially correct
6 Correct 4 ms 11356 KB Output is partially correct
7 Correct 3 ms 11356 KB Output is partially correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is partially correct
2 Correct 4 ms 11352 KB Output is partially correct
3 Correct 5 ms 11352 KB Output is partially correct
4 Correct 5 ms 11356 KB Output is partially correct
5 Correct 3 ms 11356 KB Output is partially correct
6 Correct 4 ms 11356 KB Output is partially correct
7 Correct 3 ms 11356 KB Output is partially correct
8 Correct 11 ms 14428 KB Output is partially correct
9 Correct 14 ms 15964 KB Output is partially correct
10 Correct 14 ms 16220 KB Output is partially correct
11 Correct 18 ms 19036 KB Output is partially correct