#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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
11100 KB |
Output is partially correct |
| 2 |
Execution timed out |
974 ms |
11704 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
