Submission #916939

#	Time	Username	Problem	Language	Result	Execution time	Memory
916939		andrei_iorgulescu	DEL13 (info1cup18_del13)	C++14	0 / 100	974 ms	18268 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()
{
    int parl,parr;
    if (p[1] % 2 == 1)
        parl = 0;
    else
        parl = 1;
    if ((n - p[1]) % 2 == 1)
        parr = 1;
    else
        parr = 0;
    if (parl != parr)
    {
        cout << -1 << '\n';
        return;
    }
    if (parl == 1)
    {
        cout << (n - 1) / 2 << '\n';
        int mijl = p[1] / 2;
        int cate = (n - 1) / 2;
        for (int i = 1; i <= p[1] - mijl - 1; i++)
            cout << mijl << ' ',cate--;
        int mijr = (2 * n - p[1] + 1) / 2;
        for (int i = mijr + 1; i <= n; i++)
            cout << mijr << ' ',cate--;
        for (int i = 1; i <= cate; i++)
            cout << p[1] << ' ';
        cout << '\n';
        return;
    }
    if (p[1] == 1 or p[1] == n)
    {
        if (n == 1)
        {
            cout << 0 << '\n';
            return;
        }
        cout << -1 << '\n';
        return;
    }
    int mijl = p[1] / 2;
    cout << (n - 1) / 2 << '\n';
    for (int i = 1; i < mijl; i++)
        cout << mijl << ' ';
    int dif = n - p[1];
    int mijr = n - (dif / 2) + 1;
    for (int i = 1; i < dif / 2; 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 == 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 q = nrop; q <= p[i] - p[i - 1] - 1; q += 2)
                    dp[i][j] = orr(dp[i - 1][q],dp[i][j]);
            }
            else
            {
                for (int q = nrop; q <= p[i] - p[i - 1] - 1; q += 2)
                    if (q != p[i] - p[i - 1] - 1 or p[i] - p[i - 1] - 1 == 0)
                        dp[i][j] = orr(dp[i - 1][q],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';
    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: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30