oj.uz

답안 #916939

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916939 2024-01-26T20:02:00 Z andrei_iorgulescu DEL13 (info1cup18_del13) C++14
0 / 100
 500 ms 18268 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()
{
    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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 18012 KB Execution killed with signal 11
2 Runtime error 10 ms 17844 KB Execution killed with signal 11

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 18012 KB Execution killed with signal 11
2 Runtime error 10 ms 17844 KB Execution killed with signal 11
3 Incorrect 5 ms 9136 KB Integer 0 violates the range [1, 17]
4 Correct 4 ms 9052 KB Output is partially correct

Subtask #3
0.0 / 15.0

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

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 18012 KB Execution killed with signal 11
2 Runtime error 10 ms 17844 KB Execution killed with signal 11
3 Incorrect 5 ms 9136 KB Integer 0 violates the range [1, 17]
4 Correct 4 ms 9052 KB Output is partially correct
5 Correct 3 ms 9052 KB Output is partially correct
6 Runtime error 11 ms 18036 KB Execution killed with signal 11
7 Runtime error 12 ms 18268 KB Execution killed with signal 11

Subtask #5
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 18012 KB Execution killed with signal 11
2 Runtime error 10 ms 17844 KB Execution killed with signal 11
3 Incorrect 5 ms 9136 KB Integer 0 violates the range [1, 17]
4 Correct 4 ms 9052 KB Output is partially correct
5 Correct 3 ms 9052 KB Output is partially correct
6 Runtime error 11 ms 18036 KB Execution killed with signal 11
7 Runtime error 12 ms 18268 KB Execution killed with signal 11
8 Execution timed out 553 ms 11556 KB Time limit exceeded
9 Execution timed out 661 ms 12928 KB Time limit exceeded
10 Execution timed out 537 ms 13208 KB Time limit exceeded
11 Execution timed out 553 ms 15448 KB Time limit exceeded