QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#250162#6794. Sequence to SequencezhouhuanyiAC ✓27ms8256kbC++141.3kb2023-11-12 22:15:312023-11-12 22:15:31

Judging History

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

  • [2023-11-12 22:15:31]
  • 评测
  • 测评结果:AC
  • 用时:27ms
  • 内存:8256kb
  • [2023-11-12 22:15:31]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 1000000
using namespace std;
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int T,n,a[N+1],b[N+1],tong[N+1],length;
long long ans;
int main()
{
	int l,r,sl,sr,L,R,wl,wr,d,ds;
	bool op;
	T=read();
	while (T--)
	{
		n=read(),op=length=l=r=d=ans=0;
		for (int i=1;i<=n;++i) a[i]=read();
		for (int i=1;i<=n;++i)
		{
			b[i]=read();
			if (!a[i]&&b[i]) op=1;
		}
		if (op)
		{
			puts("-1");
			continue;
		}
		for (int i=1;i<=n;++i)
			if (a[i])
				tong[++length]=i;
		for (int i=1;i<=length;++i)
		{
			if (b[tong[i]])
			{
				sl=max(a[tong[i]]-b[tong[i]],0),sr=a[tong[i]]-1,ds=d-(b[tong[i]]-a[tong[i]]),L=sl-r,R=sr-l,wl=min(ds,0),wr=max(ds,0);
				if (max(L,wl)<=min(R,wr)) ans+=abs(ds),l=max(l+wl,sl),r=min(r+wr,sr);
				else if (R<wl) ans+=abs(ds)+((wl-R)<<1),l=max(l+R,sl),r=min(r+R,sr);
				else ans+=abs(ds)+((L-wr)<<1),l=max(l+L,sl),r=min(r+L,sr);
				d=b[tong[i]]-a[tong[i]];
			}
			else
			{
				if (r>=a[tong[i]]) l=max(l,a[tong[i]]);
				else ans+=a[tong[i]]-r,d=r+d-a[tong[i]],l=r=a[tong[i]];
			}
		}
		printf("%lld\n",(ans+l+l+d)>>1);
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7904kb

input:

2
5
1 1 1 1 1
2 0 2 0 2
7
3 1 2 3 2 1 4
2 0 0 0 0 0 2

output:

3
3

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 27ms
memory: 8256kb

input:

110121
5
0 0 0 0 0
1 4 5 4 1
5
1 0 0 0 0
0 6 8 6 1
5
2 0 0 0 0
4 4 1 3 6
5
3 0 0 0 0
5 1 1 7 6
5
4 0 0 0 0
6 8 7 0 8
5
5 0 0 0 0
5 9 7 7 5
5
6 0 0 0 0
9 2 2 8 0
5
7 0 0 0 0
9 4 7 0 9
5
8 0 0 0 0
6 7 3 7 5
5
9 0 0 0 0
4 0 9 1 4
5
0 1 0 0 0
0 6 6 3 0
5
1 1 0 0 0
3 4 3 4 9
5
2 1 0 0 0
0 4 0 1 4
5
3 1 0...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 110121 tokens

Extra Test:

score: 0
Extra Test Passed