QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#639775#8551. DFS Order 5argtargWA 0ms3560kbC++203.1kb2024-10-13 22:23:082024-10-13 22:23:08

Judging History

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

  • [2024-10-13 22:23:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3560kb
  • [2024-10-13 22:23:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int, int>
void solve();

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--)solve();
    return 0;
}
//const int mod = 998244353;


void solve() {
    int n;
    int m;
    cin>>n>>m;
    vector<int>a(n+1),b(n+2);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    b[n+1]=1e18;
    sort(b.begin()+1,b.end());
    a.push_back(b[1]);

    for(int i=1;i<=n;i++){
        b[i]+=b[i-1];
    }
    sort(a.begin()+1,a.end());
    priority_queue<int,vector<int>,greater<int>>q1,q2;
    queue<int>add;
    for(int i=1;i<=n;i++){
        if(b[i]>m)break;
        auto t= lower_bound(a.begin()+1,a.end(),b[i]);
        int pre1=0,pre2=0,pre3=0;
        if(q1.size()&&q1.size()==i-1)pre1=q1.top();
        auto it=t;
        if(t!=a.end())pre2=*t-b[i];
        if(t!=a.end()&&t!=a.begin()&&i!=1){
            it--;
            pre3=*t-*it;
        }
        vector<int>sz(n+1);
        while(t!=a.end()&&(*t)<=min(m+1,b[i+1])){
            int x=*t;
            t++;

            int y=m;
            if((t!=a.end()))
                y=*t;
            if(y>min(m+1,b[i+1]))continue;
//            cout<<"y== "<<y<<endl;
            q1.push(y-x);
        }
//        cout<<q1.size()<<endl;
        while(q1.size()>i){
            q1.pop();
        }
        if(q1.size()&&pre1!=0){
            if(q1.top()>pre1){
                q1.push(pre3);
            }
            else {
//                cout<<"i== "<<i<<endl;
//                cout<<pre1<<' '<<pre2<<' '<<pre3<<endl;
//                cout<<"sz-- "<<q1.size()<<endl;
                int re=q1.top(),rre=pre1;
                if(q1.size()<i){
                    re=0;
                    //rre=0;
                }
                int tmp=pre2-re;
                int tmp2=-rre+pre3;
                if(tmp2>tmp){
                    if(sz[i-1]==i-1){
                        while(q1.top()!=pre1){
                            add.push(q1.top());
                            q1.pop();
                        }
                        q1.pop();
                        while(add.size()){
                            q1.push(add.front());
                            add.pop();
                        }
                    }
                    q1.push(pre3);
                }
                else{
                    q1.push(pre2);
                }
            }
        }
        else{
            q1.push(pre3);
        }
//        cout<<"-----------";cout<<pre1<<' '<<pre2<<' '<<pre3<<endl;
        while(q1.size()>i){
            q1.pop();
        }
        while(q1.size()&&q1.top()==0){
            q1.pop();
        }
        sz[i]=q1.size();
    }
    int ans=0;
    int sum=0;
    while(q1.size()){
        sum+=q1.top();
        q1.pop();
    }
    ans=sum;
    cout<<ans<<endl;
}
/*
2
3 13
6 7 13
1 9 999
4 14
6 7 13 14
1 9 999 999

 3
3 10
1 5 9
1 2 3
3 10
1 5 9
1 1 4
3 10
1 5 9
1 5 10
 */

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3560kb

input:

6 7
1 2
1 3
2 4
3 5
2 6
2 4 1
2 4 2
2 4 3
2 4 4
2 4 5
2 4 6
6 1 2 6 4 3 5

output:

1
1
1
5
4
4

result:

wrong answer 1st words differ - expected: 'No', found: '1'