oj.uz

답안 #916952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916952 2024-01-26T20:24:21 Z andrei_iorgulescu DEL13 (info1cup18_del13) C++14
22 / 100
 500 ms 15188 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];

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9052 KB Output is partially correct
2 Correct 3 ms 9052 KB Output is partially correct

Subtask #2
6.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9052 KB Output is partially correct
2 Correct 3 ms 9052 KB Output is partially correct
3 Correct 5 ms 9048 KB Output is partially correct
4 Correct 5 ms 9048 KB Output is partially correct

Subtask #3
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11096 KB Output is partially correct
2 Execution timed out 773 ms 11880 KB Time limit exceeded

Subtask #4
10.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9052 KB Output is partially correct
2 Correct 3 ms 9052 KB Output is partially correct
3 Correct 5 ms 9048 KB Output is partially correct
4 Correct 5 ms 9048 KB Output is partially correct
5 Correct 3 ms 9052 KB Output is partially correct
6 Correct 2 ms 9052 KB Output is partially correct
7 Correct 3 ms 9052 KB Output is partially correct

Subtask #5
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9052 KB Output is partially correct
2 Correct 3 ms 9052 KB Output is partially correct
3 Correct 5 ms 9048 KB Output is partially correct
4 Correct 5 ms 9048 KB Output is partially correct
5 Correct 3 ms 9052 KB Output is partially correct
6 Correct 2 ms 9052 KB Output is partially correct
7 Correct 3 ms 9052 KB Output is partially correct
8 Execution timed out 531 ms 11448 KB Time limit exceeded
9 Execution timed out 616 ms 12408 KB Time limit exceeded
10 Correct 500 ms 12940 KB Output is partially correct
11 Execution timed out 528 ms 15188 KB Time limit exceeded