#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
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;
| ~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9048 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9048 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9304 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13916 KB |
Output is correct |
| 2 |
Correct |
11 ms |
15704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9048 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9304 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9052 KB |
Output is correct |
| 5 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 6 |
Correct |
3 ms |
9128 KB |
Output is correct |
| 7 |
Correct |
4 ms |
9064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9048 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9304 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9052 KB |
Output is correct |
| 5 |
Correct |
3 ms |
9052 KB |
Output is correct |
| 6 |
Correct |
3 ms |
9128 KB |
Output is correct |
| 7 |
Correct |
4 ms |
9064 KB |
Output is correct |
| 8 |
Correct |
17 ms |
14368 KB |
Output is correct |
| 9 |
Correct |
19 ms |
16556 KB |
Output is correct |
| 10 |
Correct |
28 ms |
17368 KB |
Output is correct |
| 11 |
Correct |
29 ms |
21480 KB |
Output is correct |
