#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
#define pb push_back
#define fst first
#define snd second
#define all(c) (c).begin(), (c).end()
typedef long long ll;
typedef long double ld;
const ll INF64 = 1e18 + 228;
const int INF32 = 1e9 + 1337;
const int MOD = 1e9 + 7;
const ld eps = 1e-7;
const int N = 1e3 + 3;
bool check(ll &n, vector<ll> &a, vector<ll> &ans)
{
set<ll> b;
for(int i = 0; i < n; i++)
b.insert(i);
for(auto& it : ans)
{
if(b.find(it) != b.end())
{
b.erase(prev(b.find(it)));
b.erase(next(b.find(it)));
}
else
{
return 0;
}
}
for(auto& it : a)
{
if(b.find(it) != b.end())
{
continue;
}
else
{
return 0;
}
}
return (a.size() == b.size());
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// mt19937 rng(46);
// uniform_int_distribution<int> rnd;
int t;
cin >> t;
while(t--)
{
ll n, q;
cin >> n >> q;
// n = 10; q = 4;
vector<ll> a(q);
set<ll> aa;
vector<ll> pref(n, 0);
// int mask = 0;
// while(__builtin_popcount(mask) != q)
// {
// mask = rnd(rng) % (1 << n);
// }
// int itt = 0;
// for(int i = 0; i < n; i++)
// {
// if((mask >> i) & 1)
// {
// a[itt++] = i;
// aa.insert(i);
// }
// }
for(auto& it : a)
{
cin >> it;
it--;
aa.insert(it);
}
for(int i = 0; i < n; i++)
{
pref[i] = aa.count(i);
if(i) pref[i] += pref[i - 1];
}
int lst = -1;
vector< pair<ll, ll> > x;
for(auto& it : a)
{
if(lst + 1 == it)
{
lst = it;
continue;
}
x.pb({it - lst - 1, lst + 1});
lst = it;
}
if(lst != n - 1)
x.pb({n - 1 - lst, lst + 1});
vector<ll> ans;
vector<ll> fans;
for(auto& it : x)
{
if(it.fst > 4)
{
ll cnt = (it.fst - 3) / 2;
for(int i = 0; i < cnt; i++)
fans.pb(it.snd + it.fst / 2);
if(it.fst & 1)
it.fst = 3;
else
it.fst = 4;
}
}
bool bad = 0;
int lastsize = (x.size() ? x.back().fst : 0);
for(int i = 1; i < x.size(); i++)
{
if(x[i].fst == 0) continue;
if(pref[x[i].snd] - pref[x[i - 1].snd] > 1)
{
bad = 1;
break;
}
ll mn = min(x[i - 1].fst, x[i].fst);
if(x[i - 1].fst - mn)
{
fans.pb(x[i - 1].snd + x[i - 1].fst / 2);
x[i - 1].fst -= 2;
}
mn = min(x[i - 1].fst, x[i].fst);
x[i - 1].fst -= mn;
x[i].fst -= mn;
for(int j = 0; j < mn; j++)
{
ans.pb(x[i].snd - 1);
}
}
if(x.size() && x.back().fst > 1 && lastsize > 2)
{
fans.pb(x.back().snd + x.back().fst / 2);
x.back().fst -= 2;
}
for(int i = 0; i < x.size(); i++)
bad |= x[i].fst;
if(bad)
{
cout << "-1\n";
}
else
{
cout << ans.size() + fans.size() << "\n";
for(auto& it : fans)
cout << it + 1 << " ";
for(auto& it : ans)
cout << it + 1 << " ";
cout << "\n";
// bool verdict = check(n, a, ans);
// if(!verdict)
// {
// cout << "WA\n";
// return 0;
// }
// else
// cout << "OK\n";
}
}
return 0;
}
Compilation message
del13.cpp: In function 'int main()':
del13.cpp:120:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < x.size(); i++)
~~^~~~~~~~~~
del13.cpp:147:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < x.size(); i++)
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
380 KB |
Output isn't correct |
| 4 |
Incorrect |
9 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
632 KB |
Output is partially correct |
| 2 |
Correct |
9 ms |
1964 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
380 KB |
Output isn't correct |
| 4 |
Incorrect |
9 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
380 KB |
Output isn't correct |
| 4 |
Incorrect |
9 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 8 |
Incorrect |
20 ms |
1664 KB |
Output isn't correct |
| 9 |
Incorrect |
25 ms |
1900 KB |
Output isn't correct |
| 10 |
Incorrect |
25 ms |
2224 KB |
Output isn't correct |
| 11 |
Incorrect |
33 ms |
4608 KB |
Output isn't correct |
