QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#265889#2337. AzulejosInfinityNS#AC ✓480ms40652kbC++141.8kb2023-11-25 22:08:092023-11-25 22:08:10

Judging History

This is the latest submission verdict.

  • [2023-11-25 22:08:10]
  • Judged
  • Verdict: AC
  • Time: 480ms
  • Memory: 40652kb
  • [2023-11-25 22:08:09]
  • Submitted

answer

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

const int N=500050;
array<int,3> a[N],b[N];

void No(){
    printf("impossible\n");
    exit(0);
}
int main(){
    int n;
    scanf("%i",&n);
    for(int i=1;i<=n;i++){
        a[i][2]=i;
        scanf("%i",&a[i][0]);
    }
    for(int i=1;i<=n;i++){
        scanf("%i",&a[i][1]);
    }
    for(int i=1;i<=n;i++){
        b[i][2]=i;
        scanf("%i",&b[i][0]);
    }
    for(int i=1;i<=n;i++){
        scanf("%i",&b[i][1]);
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    int asz=1,bsz=1;
    set<pair<int,int>> A,B;
    vector<int> Pa,Pb;
    while(asz<=n || bsz<=n){
        if(A.empty()){
            int i;
            for(i=asz;i<=n&&a[asz][0]==a[i][0];i++){
                A.insert({a[i][1],a[i][2]});
            }
            asz=i;
        }
        if(B.empty()){
            int i;
            for(i=bsz;i<=n&&b[bsz][0]==b[i][0];i++){
                B.insert({b[i][1],b[i][2]});
            }
            bsz=i;
        }
        if(A.size()<B.size()){
            for(auto it:A){
                auto jt=B.lower_bound({it.first,0});
                if(jt==B.begin()){
                    No();
                }
                jt--;
                Pa.pb(it.second);
                Pb.pb(jt->second);
                B.erase(jt);
            }
            A.clear();
        }else{
            for(auto it:B){
                auto jt=A.upper_bound({it.first,n+5});
                if(jt==A.end()){
                    No();
                }
                Pa.pb(jt->second);
                Pb.pb(it.second);
                A.erase(jt);
            }
            B.clear();
        }
    }
    for(int x:Pa)printf("%i ",x);printf("\n");
    for(int x:Pb)printf("%i ",x);printf("\n");
    return 0;
}

Details

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 0
Accepted
time: 312ms
memory: 38924kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

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

Test #23:

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

Test #24:

score: 0
Accepted
time: 73ms
memory: 14768kb

Test #25:

score: 0
Accepted
time: 43ms
memory: 10788kb

Test #26:

score: 0
Accepted
time: 261ms
memory: 38956kb

Test #27:

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

Test #28:

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

Test #29:

score: 0
Accepted
time: 53ms
memory: 13736kb

Test #30:

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

Test #31:

score: 0
Accepted
time: 480ms
memory: 40652kb

Test #32:

score: 0
Accepted
time: 76ms
memory: 14688kb

Test #33:

score: 0
Accepted
time: 383ms
memory: 38944kb