QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246417#6794. Sequence to SequenceXZC0920AC ✓19ms9764kbC++142.4kb2023-11-10 20:06:422023-11-10 20:06:44

Judging History

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

  • [2023-11-10 20:06:44]
  • 评测
  • 测评结果:AC
  • 用时:19ms
  • 内存:9764kb
  • [2023-11-10 20:06:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const ll I=1e18;
int t,n,a[N],b[N];
ll ans,x,y,z;
namespace IO
{
    const int S=(1<<20);
    char in[S],out[S],*p1=in,*p2=in,*p3=out;
    char gc() {return p1==p2&&(p2=(p1=in)+fread(in,1,S,stdin),p1==p2)?EOF:*p1++;}
    void flush() {fwrite(out,1,p3-out,stdout);p3=out;}
    void pc(char c)
    {
        if(p3==out+S) flush();
        *p3++=c;
    }
    template<class T>void read(T &x)
    {
        x=0;int t=0;char c=gc();
        for(;!isdigit(c);c=gc()) if(c=='-') t=1;
        for(;isdigit(c);c=gc()) x=(x<<1)+(x<<3)+(c^48);
        if(t) x=-x;
    }
    template<class T>void write(T x,char c='\n')
    {
        if(x<0) pc('-'),x=-x;
        static int s[40],top=0;
        do s[++top]=x%10,x/=10;while(x);
        while(top) pc(s[top--]+48);
        pc(c);
    }
    struct F {~F(){flush();};}f;
}
using IO::read;
using IO::write;
void solve()
{
    read(n);ans=0;x=y=z=0;
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(b[i]);
    for(int i=1;i<=n;i++)
    {
        if(b[i]==0)
        {
            if(x<a[i])
            {
                ll v=min(z,a[i]-x);
                x+=v,y+=v,z-=v;ans+=v;
                if(x<a[i]) ans+=(a[i]-x),x=a[i];
            }
        }
        else
        {
            if(a[i]==0) return write(-1),void();
            if(a[i]-b[i]<=x&&b[i]-a[i]>y)
            {
                ll v=min(z,b[i]-a[i]-y);
                ans+=v,x+=v,y+=v,z-=v;
            }
            if(b[i]-a[i]<=y&&a[i]-b[i]>x)
            {
                ll v=min(z,a[i]-b[i]-x);
                ans+=v,x+=v,y+=v,z-=v;
            }
            x=min(x,(ll)a[i]-1);y=min(y,(ll)b[i]-1);
            if(a[i]-b[i]<=x&&b[i]-a[i]<=y)
            {
                if(x+b[i]-y-a[i]>=0) z=min({z,a[i]-1-x,b[i]-1-y})+(x+b[i]-y-a[i]),x=y+a[i]-b[i];
                else z=min({z,a[i]-1-x,b[i]-1-y})+(y+a[i]-x-b[i]),y=x+b[i]-a[i];
                continue;
            }
            if(a[i]-b[i]<=x)
            {
                ans+=(b[i]-a[i]-y);
                z=x;x=0;y=b[i]-a[i];
                continue;
            }
            if(b[i]-a[i]<=y)
            {
                ans+=(a[i]-b[i]-x);
                z=y;y=0;x=a[i]-b[i];
                continue;
            }
        }
    }
    write(ans);
}
int main()
{
    read(t);
    while(t--) solve();
    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7540kb

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: 19ms
memory: 9764kb

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