Submission #916952

#	Time	Username	Problem	Language	Result	Execution time	Memory
916952		andrei_iorgulescu	DEL13 (info1cup18_del13)	C++14	22 / 100	773 ms	15188 KiB

del13

#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];

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 << 0 << '\n' << '\n';*/
    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});
        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};
        }
    }
    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] << ' ';
    }
    //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)
            {
                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
            {
                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] << ' ';
        }
        //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;
}

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