Submission #916963

#	Time	Username	Problem	Language	Result	Execution time	Memory
916963		andrei_iorgulescu	DEL13 (info1cup18_del13)	C++14	100 / 100	29 ms	21480 KiB

del13

#include <bits/stdc++.h>

using namespace std;

struct ura
{
    pair<int,int>prev;
    vector<pair<int,int>>operatii;
};

int n,q,p[100005];
vector<bool> dp[100005];///pot sa fac primele i a.i sa imi las j in grupul de dupa?
vector<ura> op[100005];///voi face operatiile din x.operatii, si apoi identic cu x.prev
vector<int> cine[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);
        op[i].resize(p[i + 1] - p[i]);
        cine[i].resize(p[i + 1] - p[i],-1);
        for (int j = 0; j <= p[i + 1] - p[i] - 1; j++)
        {
            dp[i][j] = false;
            op[i][j].prev = {0,0};
            op[i][j].operatii.clear();
            cine[i][j] = -1;
        }
    }
    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;
                ///nu am efectiv nicio operatie
            }
            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;
                ///practic vreau sa fac (p[1] - 1 - nrop) / 2 operatii
                ///ce om mai bun decat (p[1] - 1 - nrop) / 2 + 1
                int om = (p[1] - 1 - nrop) / 2 + 1;
                int cateop = (p[1] - 1 - nrop) / 2;
                op[1][j].operatii.push_back({om,cateop});
                op[1][j].operatii.push_back({p[1],nrop});
                op[1][j].prev = {0,0};
            }
        }
        //cout << (int)dp[1][j] << ' ';
    }
    for (int j = p[2] - p[1] - 1; j >= 0; j--)
    {
        if (dp[1][j] == true)
            cine[1][j] = j;
        else if (j + 2 <= p[2] - p[1] - 1)
            cine[1][j] = cine[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 cn = cine[i - 1][nrop];
                    if (cn > -1)
                    {
                        dp[i][j] = true;
                        ///deci fac nrop operatii pe omul p[i], si am zis ca vin din dp[i - 1][cn]
                        ///deci am fix cn aici, din care o sa scot unele apoi fac operatiile pe i
                        int nrop2 = (cn - nrop) / 2;
                        int om = p[i - 1] + nrop2 + 1;
                        op[i][j].prev = {i - 1,cn};
                        op[i][j].operatii.push_back({om,nrop2});
                        op[i][j].operatii.push_back({p[i],nrop});
                    }
                    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 cn = cine[i - 1][nrop];
                    if (cn == -1 or (cn == p[i] - p[i - 1] - 1 and p[i] - p[i - 1] - 1 != 0))
                        dp[i][j] = false;
                    else
                    {
                        dp[i][j] = true;
                        int nrop2 = (cn - nrop) / 2;
                        int om = p[i - 1] + nrop2 + 1;
                        op[i][j].prev = {i - 1,cn};
                        op[i][j].operatii.push_back({om,nrop2});
                        op[i][j].operatii.push_back({p[i],nrop});
                    }
                }
                /*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--)
        {
            if (dp[i][j] == true)
                cine[i][j] = j;
            else if (j + 2 <= p[i + 1] - p[i] - 1)
                cine[i][j] = cine[i][j + 2];
        }
        //cout << '\n';
    }
    bool ans = false;
    int unde;
    for (int i = 0; i <= n - p[q]; i += 2)
    {
        if (i != n - p[q])
        {
            ans = orr(ans,dp[q][i]);
            if (dp[q][i] == true)
                unde = i;
        }
        else if (n == p[q])
        {
            ans = orr(ans,dp[q][i]);
            if (dp[q][i] == true)
                unde = i;
        }
    }
    if (ans == true)
    {
        vector<pair<int,int>>op1,op2;
        int opfin = unde / 2;
        op1.push_back({p[q] + opfin + 1,opfin});
        pair<int,int>cur = {q,unde};
        while (cur.first != 0)
        {
            if (op[cur.first][cur.second].operatii.size() == 2)
            {
                op1.push_back(op[cur.first][cur.second].operatii[0]);
                op2.push_back(op[cur.first][cur.second].operatii[1]);
            }
            cur = op[cur.first][cur.second].prev;
        }
        cout << (n - q) / 2 << '\n';
        for (auto it : op1)
        {
            for (int i = 1; i <= it.second; i++)
                cout << it.first << ' ';
        }
        for (auto it : op2)
        {
            for (int i = 1; i <= it.second; i++)
                cout << it.first << ' ';
        }
        cout << '\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;
}

Compilation message (stderr)

del13.cpp: In function 'void testcase()':
del13.cpp:227:26: warning: 'unde' may be used uninitialized in this function [-Wmaybe-uninitialized]
  227 |         int opfin = unde / 2;
      |                     ~~~~~^~~

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