QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#230453#6420. Certain Scientific RailgunGFFFWA 1ms9904kbC++145.7kb2023-10-28 18:54:432023-10-28 18:54:44

Judging History

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

  • [2023-10-28 18:54:44]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：9904kb
查看
  • [2023-10-28 18:54:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const ll INF=1e18;
const int maxn=1e5+5;
ll ans;
int T,n,cnt,pos[maxn];
struct P{
    int x,y;
    void rotate()
    {
        y=-y;
        swap(x,y);
    }
    bool friend operator < (const P a,const P b) {return a.x<b.x;}
}t[maxn];
struct dn{
    int id,l,r;
}tl[maxn],tr[maxn];
bool cmp1(const dn a,const dn b) {return a.l>b.l;}
bool cmp2(const dn a,const dn b) {return a.r<b.r;}
struct C{
    int id,mn,mx;
    ll w;
    bool friend operator < (const C a,const C b) {return a.w<b.w;}
};
set<C> S[3][2];
vector<P> fr,se;
void R() {for(int i=1;i<=n;++i) t[i].rotate();}
void clear()
{
    for(int i=0;i<=2;++i)
        for(int j=0;j<=min(1ll,i);++j)
            S[i][j].clear();
    fr.clear();se.clear();
    for(int i=1;i<=n;++i) pos[i]=-1;
}
void work()
{
    ll X=INF;
    for(int i=1;i<=n;++i)
        if(t[i].x<0) fr.push_back(t[i]);
        else se.push_back(t[i]);
    sort(fr.begin(),fr.end());
    sort(se.begin(),se.end());
    int L=fr.size(),R=se.size();
    if(!L) return ;
    if(!R)
    {
        int l=0,r=0;
        for(int i=1;i<=L;++i)
        {
            P x=fr[i-1];
            ans=min(ans,(ll)abs(l)+r+min(abs(l),r)+abs(x.x));
            l=min(l,x.y);
            r=max(r,x.y);
        }
        return ;
    }
    int l=0,r=0;
    for(int i=R;i;--i)
    {
        P x=se[i-1];
        pos[i]=0;
        S[0][0].insert((C){i,l,r,abs(x.x)+abs(l)+abs(r)+min(abs(l),abs(r))});
        tl[i]=(dn){i,l,r};
        tr[i]=(dn){i,l,r};
        l=min(l,x.y);
        r=max(r,x.y);
    }
    int LL=l,RR=r,pl=0,pr=0;
    l=r=0;
    sort(tl+1,tl+R+1,cmp1);
    sort(tr+1,tr+R+1,cmp2);
    while(pl+1<=R&&tl[pl+1].l>=l)
    {
        ++pl;
        if(!pos[tl[pl].id])
        {
            pos[tl[pl].id]=2;
            S[2][0].insert((C){tl[pl].id,tl[pl].l,tl[pl].r,abs((ll)se[tl[pl].id-1].x)+abs(tl[pl].r)});
            S[2][1].insert((C){tl[pl].id,tl[pl].l,tl[pl].r,abs((ll)se[tl[pl].id-1].x)+2ll*abs(tl[pl].r)});
        }
        else
        {
            pos[tr[pl].id]=3;
            X=min(X,abs((ll)se[tl[pl].id-1].x));
        }
    }
    while(pr+1<=R&&tr[pr+1].r<=r)
    {
        ++pr;
        if(!pos[tr[pr].id])
        {
            pos[tr[pr].id]=1;
            S[1][0].insert((C){tr[pr].id,tr[pr].l,tr[pr].r,abs((ll)se[tr[pr].id-1].x)+abs(tr[pr].l)});
            S[1][1].insert((C){tr[pr].id,tr[pr].l,tr[pr].r,abs((ll)se[tr[pr].id-1].x)+2ll*abs(tr[pr].l)});
        }
        else
        {
            pos[tr[pr].id]=3;
            X=min(X,abs((ll)se[tr[pr].id-1].x));
        }
    }
    l=0,r=0;
    for(int i=1;i<=L;++i)
    {
        P x=fr[i-1];
        for(int i=0;i<=2;++i)
            for(int j=0;j<=min(1ll,i);++j)
                if(S[i][j].size())
                {
                    while(S[i][j].size()&&pos[(*S[i][j].begin()).id]!=i)
                    {
                        auto ttt=S[i][j].begin();
                        S[i][j].erase(ttt);
                    }
                }
        if(S[0][0].size())
        {
            C now=*S[0][0].begin();
            ans=min(ans,2ll*abs(x.x)+now.w);
        }
        if(S[1][0].size())
        {
            C now=*S[1][0].begin();
            ans=min(ans,2ll*abs(x.x)+now.w+2ll*r);
        }
        if(S[1][1].size())
        {
            C now=*S[1][1].begin();
            ans=min(ans,2ll*abs(x.x)+now.w+r);
        }
        if(S[2][0].size())
        {
            C now=*S[2][0].begin();
            ans=min(ans,2ll*abs(x.x)+now.w+2ll*abs(l));
        }
        if(S[2][1].size())
        {
            C now=*S[2][1].begin();
            ans=min(ans,2ll*abs(x.x)+now.w+abs(l));
        }
        ans=min(ans,2ll*abs(x.x)+X+abs(l)+abs(r)+min(abs(l),abs(r)));
        ans=min(ans,(ll)abs(x.x)+max(abs(l),abs(LL))+max(abs(r),abs(RR))+min(max(abs(l),abs(LL)),max(abs(r),abs(RR))));
        l=min(l,x.y);
        r=max(r,x.y);
        while(pl+1<=R&&tl[pl+1].l>=l)
        {
            ++pl;
            if(!pos[tl[pl].id])
            {
                pos[tl[pl].id]=2;
                S[2][0].insert((C){tl[pl].id,tl[pl].l,tl[pl].r,abs((ll)se[tl[pl].id-1].x)+abs(tl[pl].r)});
                S[2][1].insert((C){tl[pl].id,tl[pl].l,tl[pl].r,abs((ll)se[tl[pl].id-1].x)+2ll*abs(tl[pl].r)});
            }
            else
            {
                pos[tr[pl].id]=3;
                X=min(X,abs((ll)se[tl[pl].id-1].x));
            }
        }
        while(pr+1<=R&&tr[pr+1].r<=r)
        {
            ++pr;
            if(!pos[tr[pr].id])
            {
                pos[tr[pr].id]=1;
                S[1][0].insert((C){tr[pr].id,tr[pr].l,tr[pr].r,abs((ll)se[tr[pr].id-1].x)+abs(tr[pr].l)});
                S[1][1].insert((C){tr[pr].id,tr[pr].l,tr[pr].r,abs((ll)se[tr[pr].id-1].x)+2ll*abs(tr[pr].l)});
            }
            else
            {
                pos[tr[pr].id]=3;
                X=min(X,abs((ll)se[tr[pr].id-1].x));
            }
        }
    }
}
signed main()
{
    scanf("%lld",&T);
    while(T--)
    {
        ans=1e18;
        scanf("%lld",&n);
        cnt=0;
        for(int i=1,x,y;i<=n;++i) 
        {
            scanf("%lld%lld",&x,&y);
            if(x!=0&&y!=0) t[++cnt]=(P){x,y};
        }
        if(!cnt) {puts("0");continue;}
        n=cnt;
        work();
        clear();
        R();
        work();
        clear();
        R();
        work();
        clear();
        R();
        work();
        clear();
        cout<<ans<<endl;
    }
    return 0;
}
/*
3
2
0 1
1 0
4
1 1
-3 -3
4 -4
-2 2
4
1 100
3 100
-100 1
3 -100

1
4
1 1
-3 -3
4 -4
-2 2

*/
源文件, 语言: C++14

详细

Test #1:

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

input:

3
2
0 1
1 0
4
1 1
-3 -3
4 -4
-2 2
4
1 100
3 100
-100 1
3 -100

output:

0
8
4

result:

ok 3 number(s): "0 8 4"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 9904kb

input:

120
4
11 11
-22 -22
33 -33
-44 44
4
-11 11
22 -22
-33 -33
44 44
4
-11 -11
22 22
-33 33
44 -44
4
11 -11
-22 22
33 33
-44 -44
4
-11 11
22 -22
33 33
-44 -44
4
11 11
-22 -22
-33 33
44 -44
4
11 -11
-22 22
-33 -33
44 44
4
-11 -11
22 22
33 -33
-44 44
4
1 1
-2 -2
3 -3
-4 4
4
-1 1
2 -2
-3 -3
4 4
4
-1 -1
2 2
...

output:

99
99
99
99
99
99
99
99
9
9
9
9
9
9
9
9
5
5
5
5
5
5
5
5
4
4
4
4
4
4
4
4
0
0
0
0
0
0
0
0
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
12
12
12
12
12
12
12
12
0
0
0
0
0
0
0
0
8
11
8
11
8
11
8
11
111
111
111
111
111
111
111
111
300
300
300
300
300
300
300
300
5
5
5
5
5
5
5
5
2
2
2
2
2
2
2
2
48
48
48
48
48
48
48
48

result:

wrong answer 73rd numbers differ - expected: '11', found: '8'
English 繁體中文 简体中文

服务器时间: 2024-12-02 22:48:46 | 开源项目