QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#377928#2337. AzulejosUFRJ#WA 0ms3528kbC++142.4kb2024-04-05 20:27:042024-04-05 20:27:05

Judging History

This is the latest submission verdict.

  • [2024-04-05 20:27:05]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3528kb
  • [2024-04-05 20:27:04]
  • Submitted

answer

#include "bits/stdc++.h"

using namespace std;
using lint = int64_t;

int main(void) {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int>p1(n), h1(n), p2(n), h2(n);
    for(int i=0;i<n;i++) cin>>p1[i];
    for(int i=0;i<n;i++) cin>>h1[i];
    for(int i=0;i<n;i++) cin>>p2[i];
    for(int i=0;i<n;i++) cin>>h2[i];
    vector<int>o1(n), o2(n);
    for(int i=0;i<n;i++) o1[i] = o2[i] = i;
    sort(o1.begin(), o1.end(), [&](int i, int j){
        if(h1[i] == h1[j]){
            return p1[i] < p1[j];
        }
        return h1[i] < h1[j];
    });

    sort(o2.begin(), o2.end(), [&](int i, int j){
        if(h2[i] == h2[j]){
            return p2[i] < p2[j];
        }
        return h2[i] < h2[j];
    });
    set<pair<int, int>>s, t;
    vector<int>a1, a2;
    for(int l=0,r=0;r<n;){
        if(s.empty()){
            int c = p1[o1[l]];
            while(l < n && p1[o1[l]] == c){
                s.insert({h1[o1[l]], o1[l]});
                l++;
            }
        }
        if(t.empty()){
            int c = p2[o2[r]];
            while(r < n && p2[o2[r]] == c){
                t.insert({h2[o2[r]], o2[r]});
                r++;
            }
        }
        if(s.size() <= t.size()){
            while(!s.empty()){
                auto [_, i] = *s.begin();
                s.erase(s.begin());
                auto it = t.lower_bound({h1[i], 0});
                if(it == t.begin()){
                    cout<<"impossible\n";
                    return 0;
                }
                it--;
                auto [__, j] = *it;
                t.erase(it);
                a1.push_back(i+1);
                a2.push_back(j+1);
            }
        }
        else{
            while(!t.empty()){
                auto [_, i] = *t.begin();
                t.erase(t.begin());
                auto it = s.lower_bound({h2[i] + 1, 0});
                if(it == s.end()){
                    cout<<"impossible\n";
                    return 0;
                }
                auto [__, j] = *it;
                s.erase(it);
                a1.push_back(j+1);
                a2.push_back(i+1);
            }
        }
    }
    reverse(a1.begin(), a1.end());
    reverse(a2.begin(), a2.end());
    for(int i=0;i<n;i++) cout<<a1[i]<<" ";
    cout<<"\n";
    for(int i=0;i<n;i++) cout<<a2[i]<<" ";
    cout<<"\n";
    return 0;
}

Details

Test #1:

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