QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#229508#7615. Sequence FoldingwxqwqWA 0ms7704kbC++141.2kb2023-10-28 16:19:472023-10-28 16:19:47

Judging History

你现在查看的是最新测评结果

  • [2023-10-28 16:19:47]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7704kb
  • [2023-10-28 16:19:47]
  • 提交

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'