| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 689808 | 2023-01-29T12:17:21 Z | alexdd | DEL13 (info1cup18_del13) | C++17 | 8 ms | 2236 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int v[100005];
int gap[100005];
vector<int> sol;
vector<int> sol2;
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int t;
cin>>t;
while(t--)
{
sol.clear();
sol2.clear();
cin>>n>>q;
for(int i=1;i<=q;i++)
{
cin>>v[i];
gap[i-1]=v[i]-v[i-1]-1;
}
if(q==0)
{
cout<<-1<<"\n";
continue;
}
gap[q] = n - v[q];
q++;
v[q] = n+1;
bool impossible=0;
for(int i=1;i<q;i++)
{
if(impossible)
break;
if(gap[i-1]==0 || gap[i]==0)
continue;
if(gap[i-1]%2==1 && gap[i]>=1 && gap[i-1]>=1)///daca trebuie sa scad 1
{
sol.push_back(v[i]);
gap[i]--;
gap[i-1]--;
}
}
for(int i=0;i<q;i++)
if(gap[i]%2==1)
impossible=1;
int inc = 0;
for(int i=0;i<q;i++)
{
if(impossible)
break;
if(gap[i]==0)
{
if(inc!=i)
{
if((i-inc)%2==0)
{
for(int j=inc;j<i;j+=2)
{
sol.push_back(v[j+1]);
sol.push_back(v[j+1]);
gap[j]-=2;
gap[j+1]-=2;
}
}
else
{
int mxm=0,unde=-1;
bool avem=0;
int unde_avem=-1;
for(int j=inc;j<i;j++)
{
if((inc-j)%2==0 && gap[j]!=v[j+1]-v[j]-1)
{
avem=1;
unde_avem=j;
}
if(j>inc && j<i-1 && gap[j]>mxm)
{
mxm=gap[j];
unde=j;
}
}
if(avem)
{
int cate=0;
for(int j=inc;j<i;j++)
{
if(j!=unde_avem)
cate++;
if(cate%2==1)
{
sol.push_back(v[j+1]);
sol.push_back(v[j+1]);
gap[j]-=2;
gap[j+1]-=2;
}
}
}
else
{
if(mxm<4)
impossible=1;
else
{
for(int j=unde;j<i;j+=2)
{
sol.push_back(v[j+1]);
sol.push_back(v[j+1]);
gap[j]-=2;
gap[j+1]-=2;
}
for(int j=inc;j<unde;j+=2)
{
sol.push_back(v[j+1]);
sol.push_back(v[j+1]);
gap[j]-=2;
gap[j+1]-=2;
}
}
}
}
}
inc=i+1;
}
}
if(!impossible)
{
for(int i=0;i<q;i++)
{
if(gap[i]==0)
continue;
if(gap[i]<0 || gap[i]%2==1 || gap[i]==v[i+1]-v[i]-1)
{
impossible=1;
break;
}
int mij=(v[i+1]+v[i])/2;
while(gap[i]>0)
{
sol2.push_back(mij);
gap[i]-=2;
}
}
}
if(impossible)
{
cout<<-1<<"\n";
continue;
}
cout<<sol.size() + sol2.size()<<"\n";
for(int i=0;i<sol2.size();i++)
cout<<sol2[i]<<" ";
for(int i=0;i<sol.size();i++)
cout<<sol[i]<<" ";
cout<<"\n";
}
return 0;
}
/**
cazuri pe care nu merge solutia:
1
20 6
4 12 15 18 19 20
my solution: -1
*/
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
| 2 | Incorrect | 1 ms | 340 KB | Output isn't correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
| 2 | Incorrect | 1 ms | 340 KB | Output isn't correct |
| 3 | Incorrect | 4 ms | 344 KB | Output isn't correct |
| 4 | Incorrect | 4 ms | 340 KB | Output isn't correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 5 ms | 580 KB | Output isn't correct |
| 2 | Incorrect | 1 ms | 340 KB | Output isn't correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
| 2 | Incorrect | 1 ms | 340 KB | Output isn't correct |
| 3 | Incorrect | 4 ms | 344 KB | Output isn't correct |
| 4 | Incorrect | 4 ms | 340 KB | Output isn't correct |
| 5 | Correct | 1 ms | 336 KB | Output is correct |
| 6 | Incorrect | 1 ms | 340 KB | Output isn't correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
| 2 | Incorrect | 1 ms | 340 KB | Output isn't correct |
| 3 | Incorrect | 4 ms | 344 KB | Output isn't correct |
| 4 | Incorrect | 4 ms | 340 KB | Output isn't correct |
| 5 | Correct | 1 ms | 336 KB | Output is correct |
| 6 | Incorrect | 1 ms | 340 KB | Output isn't correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Incorrect | 7 ms | 732 KB | Output isn't correct |
| 9 | Incorrect | 6 ms | 972 KB | Output isn't correct |
| 10 | Incorrect | 6 ms | 1104 KB | Output isn't correct |
| 11 | Incorrect | 8 ms | 2236 KB | Output isn't correct |