QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#229508 | #7615. Sequence Folding | wxqwq | WA | 0ms | 7704kb | C++14 | 1.2kb | 2023-10-28 16:19:47 | 2023-10-28 16:19:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL n,m;
LL f[N][2],g[N][2];
LL q[N],tmp[N];
inline LL get(LL x,int k)
{
if(x<(1ll<<(k-1))) return x;
return (1ll<<k)-1-x;
}
int main()
{
scanf("%lld%lld",&n,&m);
int cnt=0;
for(LL i=1,x;i<=m;i++){
scanf("%lld",&x),--x;
q[++cnt]=x,f[cnt][0]=1,f[cnt][1]=0;
}
LL dep=-1,t=n;
while(t) ++dep,t>>=1;
for(int k=dep;k;k--)
{
int tcnt=0;
for(int i=1,j=cnt;i<=j;){
LL x=get(q[i],k),y=get(q[j],k);
// cout<<x<<' '<<k<<' '<<q[i]<<' '<<i<<endl;
// cout<<y<<' '<<k<<' '<<q[j]<<' '<<j<<endl;
if(x==y){
tmp[++tcnt]=x;
g[tcnt][0]=f[i][0]+(i!=j?f[j][0]:0);
g[tcnt][1]=f[i][1]+(i!=j?f[j][1]:1);
// if(i==j) cout<<g[tcnt][1]<<endl;
++i,--j;
}
else if(x<y){
tmp[++tcnt]=x;
g[tcnt][1]=f[i][1]+1;
g[tcnt][0]=f[i][0];
++i;
}
else{
tmp[++tcnt]=y;
g[tcnt][1]=f[j][1]+1;
g[tcnt][0]=f[j][0];
--j;
}
}
memcpy(f,g,sizeof(f));
memcpy(q,tmp,sizeof(tmp));
cnt=tcnt;
// for(int i=1;i<=cnt;i++) cout<<q[i]<<' '<<f[i][1]<<endl;
}
printf("%d\n",min(f[1][0],f[1][1])-1);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 7704kb
input:
8 3 1 5 8
output:
1
result:
wrong answer 1st lines differ - expected: '2', found: '1'