QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#60014#2337. Azulejoscaptured#WA 3ms5760kbC++172.8kb2022-11-02 17:20:302022-11-02 17:20:32

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-02 17:20:32]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 5760kb
  • [2022-11-02 17:20:30]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;




const int maxn = 5e5+5;
struct D {
    int p, h, idx;
} bck[maxn], frnt[maxn];

bool cmp(const D &a, const D &b) {
    if (a.p == b.p) {
        return a.h < b.h;
    }
    return a.p < b.p;
}
bool operator > (const pair<int, D> a, const pair<int, D> b) {
    return a.first > b.first;
}
void solve(int cs){
    int n, x;
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>x;
        bck[i].p = x;
    }
    for (int i = 1; i <= n; i++) {
        cin>>x;
        bck[i].h = x;
        bck[i].idx = i;
    }
    for (int i = 1; i <= n; i++) {
        cin>>x;
        frnt[i].p = x;
    }
    for (int i = 1; i <= n; i++) {
        cin>>x;
        frnt[i].h = x;
        frnt[i].idx = i;
    }
    sort(frnt+1, frnt+n+1, cmp);
    sort(bck+1, bck+n+1, cmp);
    int f = 0, j = 1;
    stack<D> q;
    priority_queue<pair<int, int>> pq;
    q.push(bck[1]);
    vector<int> ans, ans2;

    for (int i = 2; i<= n; i++) {
        if (bck[i].p==bck[i-1].p) {
            q.push(bck[i]);
        }
        else {
            while (j < i) {
                pq.push({frnt[j].h, frnt[j].idx});
                j++;
            }
            while (j <= n && frnt[j].h < q.top().h && frnt[j].p == frnt[j-1].p) {
                pq.push({frnt[j].h, frnt[j].idx});
                j++;
            }
            while (q.empty()==0) {
//                cout<<pq.top().first<<" "<<q.top().h<<endl;
                if (pq.top().first < q.top().h) {
                    ans.push_back(q.top().idx);
                    ans2.push_back(pq.top().second);
                }
                else {
                    f = 1;
                }
                pq.pop();
                q.pop();
            }
            q.push(bck[i]);
        }
    }
    while (j <= n) {
        pq.push({frnt[j].h, frnt[j].idx});
        j++;
    }
    while (j <= n && frnt[j].h < q.top().h && frnt[j].p == frnt[j-1].p) {
        pq.push({frnt[j].h, frnt[j].idx});
        j++;
    }
    while (q.empty()==0) {
//        cout<<pq.top().first<<" "<<q.top().h<<endl;
        if (pq.top().first < q.top().h) {
            ans.push_back(q.top().idx);
            ans2.push_back(pq.top().second);
        }
        else {
            f = 1;
        }
        pq.pop();
        q.pop();
    }

    if (f == 1) {
        cout<<"impossible\n";
        return;
    }
    for (int i = 1; i<=n; i++) {
        cout<<ans[i-1]<<" ";
    }
    cout<<"\n";
    for (int i = 1; i<=n; i++) {
        cout<<ans2[i-1]<<" ";
    }
    cout<<"\n";
}


int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t;t=1;
    //cin>>t;
    for(int cs=1;cs<=t;cs++)solve(cs);
    return 0;
}


詳細信息

Test #1:

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

Test #2:

score: 0
Accepted
time: 2ms
memory: 5588kb

Test #3:

score: 0
Accepted
time: 3ms
memory: 5760kb

Test #4:

score: 0
Accepted
time: 2ms
memory: 5688kb

Test #5:

score: 0
Accepted
time: 2ms
memory: 5688kb

Test #6:

score: 0
Accepted
time: 1ms
memory: 5624kb

Test #7:

score: 0
Accepted
time: 2ms
memory: 5696kb

Test #8:

score: -100
Wrong Answer
time: 2ms
memory: 5588kb