# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
317945 | daniel920712 | DEL13 (info1cup18_del13) | C++14 | 41 ms | 4192 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
using namespace std;
int all[100005];
int Father[1000005];
int Father2[1000005];
int xx[1000005]={0};
bool have[1000005]={0};
bool can[1000005]={0};
bool use[5][1000005]={0};
int DP[5][1000005]={0};
pair < int , int > Next[5][1000005];
vector < int > tt;
vector < int > ttt;
vector < int > ans;
set < int > temp;
int T,N,M;
stack < int > aaa;
bool F(int can,int here)
{
if(here==M+1) return 1-can;
if(can==1&&ttt[here]<2) return 0;
if(ttt[here]==0)
{
Next[can][here]=make_pair(0,here+1);
return F(0,here+1);
}
if(use[can][here]) return DP[can][here];
DP[can][here]=0;
if(can==1)
{
if(ttt[here]>=4)
{
if(F(1,here+1))
{
Next[can][here]=make_pair(1,here+1);
DP[can][here]=1;
}
}
if(F(0,here+1))
{
Next[can][here]=make_pair(0,here+1);
DP[can][here]=1;
}
}
else
{
if(F(1,here+1))
{
Next[can][here]=make_pair(1,here+1);
DP[can][here]=1;
}
}
if(::can[here])
{
if(F(0,here+1))
{
Next[can][here]=make_pair(0,here+1);
DP[can][here]=1;
}
}
use[can][here]=1;
return DP[can][here];
}
void FF(int can,int here)
{
//printf("%d %d\n",can,here);
if(here==M+1) return;
FF(Next[can][here].first,Next[can][here].second);
if(Next[can][here].first) xx[here+1]+=2;
}
void Find(int here)
{
int i;
//printf("%d\n",here);
if(have[here]) return;
have[here]=1;
vector < int > tt;
for(i=0;i<N;i++)
{
if(here&(1<<i)) tt.push_back(i);
}
for(i=1;i<tt.size()-1;i++)
{
Father[here-(1<<tt[i-1])-(1<<tt[i+1])]=here;
Father2[here-(1<<tt[i-1])-(1<<tt[i+1])]=tt[i];
Find(here-(1<<tt[i-1])-(1<<tt[i+1]));
}
}
int main()
{
int i,j,con,ok=0,last,tt=0,ff=0,where;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&N,&M);
ok=1;
all[0]=0;
for(i=1;i<=M;i++) scanf("%d",&all[i]);
all[M+1]=N+1;
ttt.clear();
for(i=0;i<=M;i++)
{
xx[i]=0;
can[i]=0;
ttt.push_back(all[i+1]-all[i]-1);
}
for(i=0;i<=M;i++)
{
use[0][i]=0;
use[1][i]=0;
if(ttt[i]%2)
{
if(i!=M&&ttt[i+1]>=1)
{
can[i]=1;
can[i+1]=1;
ttt[i]--;
ttt[i+1]--;
xx[i+1]++;
}
}
if(ttt[i]%2) break;
}
if(i!=M+1)
{
printf("-1\n");
continue;
}
if(F(0,0)==0) printf("-1\n");
else
{
FF(0,0);
ans.clear();
for(i=0;i<=M;i++)
{
temp.clear();
for(j=all[i]+1;j<all[i+1];j++) temp.insert(j);
N=temp.size();
N-=xx[i];
N-=xx[i+1];
//printf("%d %d %d\n",all[i],all[i+1],N);
for(j=0;j<N/2;j++)
{
tt=*next(temp.begin());
ans.push_back(tt);
temp.erase(temp.upper_bound(tt));
temp.erase(prev(temp.lower_bound(tt)));
}
}
for(i=0;i<=M;i++) while(xx[i]--) ans.push_back(all[i]);
printf("%d\n",ans.size());
for(auto i:ans) printf("%d ",i);
printf("\n");
}
ok=1;
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |