# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
317225 | daniel920712 | DEL13 (info1cup18_del13) | C++14 | 20 ms | 1672 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <map>
#include <stack>
using namespace std;
int all[100005];
int Father[1000005];
int Father2[1000005];
bool have[1000005]={0};
vector < int > tt;
vector < int > ans;
int T,N,M;
stack < int > aaa;
int F(int l,int r)
{
int x,ok=1,i,y;
tt.clear();
while(!aaa.empty()) aaa.pop();
for(i=l;i<=r;i++)
{
if(i==0)
{
if(all[i]!=1) tt.push_back(all[i]-1);
}
else if(all[i]-all[i-1]-1) tt.push_back(all[i]-all[i-1]-1);
}
if(r==M-1)
{
if(all[r]!=N) tt.push_back(N-all[r]);
}
else if(all[r+1]-all[r]-1)
{
tt.push_back(all[r+1]-all[r]-1);
}
if(tt.empty()) return 1;
if(tt.size()==1) return 0;
x=0;
for(auto i:tt)
{
x+=i;
if(i%2==0)
{
if(!aaa.empty()&&aaa.top()==0) aaa.pop();
else aaa.push(0);
}
else aaa.push(1);
}
if(x%2==1) return 0;
if(aaa.empty()) return 1;
x=aaa.top();
while(!aaa.empty())
{
y=aaa.top();
aaa.pop();
}
if(x==0||y==0) return 0;
return 1;
}
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]));
}
}
void FF(int here)
{
int i;
//printf("%d\n",here);
if(here==(1<<N)-1) return;
FF(Father[here]);
ans.push_back(Father2[here]);
}
int main()
{
int i,j,con,xx=0,ok=0,last,tt=0,ff=0,where;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&N,&M);
//printf("%d %d %d\n",N,ff,ok);
if((!ok||N==ff)&&N<=18)
{
//printf("aa\n");
if(!ok)
{
ff=N;
Find((1<<N)-1);
ok=1;
}
tt=0;
for(i=0;i<M;i++)
{
scanf("%d",&all[i]);
all[i]--;
tt+=(1<<all[i]);
}
if(have[tt])
{
ans.clear();
FF(tt);
printf("%d\n",ans.size());
for(auto i:ans) printf("%d ",i+1);
printf("\n");
}
else printf("-1\n");
}
else
{
ok=1;
last=0;
for(i=1;i<=N;i++) have[i]=0;
for(i=0;i<M;i++)
{
scanf("%d",&all[i]);
have[all[i]]=1;
}
if((N-M)%2) printf("-1\n");
else
{
for(i=1;i<M;i++)
{
if(all[i]-all[i-1]==1)
{
ok=ok&F(last,i-1);
last=i;
}
}
ok=ok&&F(last,M-1);
if(ok==0) printf("%d\n",ok-1);
else
{
for(i=2;i<N;i++)
{
if(have[i-1]==0&&have[i+1]==0)
{
printf("1\n%d\n",i);
}
}
}
}
ok=1;
}
}
return 0;
}
컴파일 시 표준 에러 (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... |