QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#377931#2337. AzulejosUFRJ#AC ✓420ms40420kbC++142.3kb2024-04-05 20:30:072024-04-05 20:30:09

Judging History

This is the latest submission verdict.

  • [2024-04-05 20:30:09]
  • Judged
  • Verdict: AC
  • Time: 420ms
  • Memory: 40420kb
  • [2024-04-05 20:30:07]
  • 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(p1[i] == p1[j]){
            return h1[i] < h1[j];
        }
        return p1[i] < p1[j];
    });

    sort(o2.begin(), o2.end(), [&](int i, int j){
        if(p2[i] == p2[j]){
            return h2[i] < h2[j];
        }
        return p2[i] < p2[j];
    });
    set<pair<int, int>>s, t;
    vector<int>a1, a2;
    for(int l=0,r=0;l<n || 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);
            }
        }
    }
    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: 100
Accepted
time: 0ms
memory: 3756kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 3748kb

Test #3:

score: 0
Accepted
time: 0ms
memory: 3620kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 3556kb

Test #5:

score: 0
Accepted
time: 0ms
memory: 3596kb

Test #6:

score: 0
Accepted
time: 0ms
memory: 3620kb

Test #7:

score: 0
Accepted
time: 0ms
memory: 3536kb

Test #8:

score: 0
Accepted
time: 0ms
memory: 3784kb

Test #9:

score: 0
Accepted
time: 0ms
memory: 3600kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 3624kb

Test #11:

score: 0
Accepted
time: 0ms
memory: 3828kb

Test #12:

score: 0
Accepted
time: 272ms
memory: 38224kb

Test #13:

score: 0
Accepted
time: 0ms
memory: 3540kb

Test #14:

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

Test #15:

score: 0
Accepted
time: 4ms
memory: 4540kb

Test #16:

score: 0
Accepted
time: 0ms
memory: 3752kb

Test #17:

score: 0
Accepted
time: 0ms
memory: 3492kb

Test #18:

score: 0
Accepted
time: 0ms
memory: 3528kb

Test #19:

score: 0
Accepted
time: 0ms
memory: 3832kb

Test #20:

score: 0
Accepted
time: 0ms
memory: 3748kb

Test #21:

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

Test #22:

score: 0
Accepted
time: 56ms
memory: 6700kb

Test #23:

score: 0
Accepted
time: 45ms
memory: 9616kb

Test #24:

score: 0
Accepted
time: 64ms
memory: 9704kb

Test #25:

score: 0
Accepted
time: 39ms
memory: 6608kb

Test #26:

score: 0
Accepted
time: 213ms
memory: 38160kb

Test #27:

score: 0
Accepted
time: 48ms
memory: 10156kb

Test #28:

score: 0
Accepted
time: 60ms
memory: 10160kb

Test #29:

score: 0
Accepted
time: 49ms
memory: 10292kb

Test #30:

score: 0
Accepted
time: 34ms
memory: 10296kb

Test #31:

score: 0
Accepted
time: 420ms
memory: 40420kb

Test #32:

score: 0
Accepted
time: 60ms
memory: 10276kb

Test #33:

score: 0
Accepted
time: 376ms
memory: 38192kb