QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#60105#2337. AzulejoscapturedRE 0ms0kbC++173.8kb2022-11-02 21:01:302022-11-02 21:01:31

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 21:01:31]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2022-11-02 21:01:30]
  • Submitted

answer

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

#define endl "\n"


const int maxn = 5e5+5;
struct D {
    int p, h, idx;
} bck[maxn], frnt[maxn], X[maxn], Y[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 cmp2 (const pair<int, pair<int, int>> a, const pair<int, pair<int, int>> b) {
    if (X[a.second.first].p == X[b.second.first].p) {
        return Y[a.second.second].p < Y[b.second.second].p;
    }
    return X[a.second.first].p < X[b.second.first].p;
}





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;
        X[i] = bck[i];
        Y[i] = frnt[i];
    }
    sort(frnt+1, frnt+n+1, cmp);
    sort(bck+1, bck+n+1, cmp);
    int f = 0, j = 1;
//    map<int, multiset<pair<int, int>>> mp, mp2;
//
//    for (int i = 1; i <= n; i++) {
//        mp[bck[i].p].insert({bck[i].h, bck[i].idx});
//    }
//    for (int i = 1; i <= n; i++) {
//        mp2[frnt[i].p].insert({frnt[i].h, frnt[i].idx});
//    }
//    auto bc = mp.begin(), fr = mp2.begin();
//    vector<pair<int, int>> ans;
//    while (bc != mp.end() && fr != mp2.end()) {
//        vector<pair<int, int> > tmp;
//        for (auto x: fr.first) {
//            if (bc.first.upper_bound(x.first) != bc.first.end()) {
//                bc.first.erase()
//            }
//        }
//    }
    stack<pair<int, int > >st;
    int pointerr = 1;
    int pointerr2 = 1;
    multiset <pair <int, int> >mp;
    vector<int> ans1 ,ans2;
    for(int  i  = 1; i <= n; i++)
    {
        if(st.empty())
        {
            int  j = pointerr;
            while(j <= n)
            {
                if(bck[j].p == bck[pointerr].p)
                {
                    st.push({bck[j].h , bck[j].idx});
                    j++;
                }
                else
                    break;
            }
            pointerr = j;
        }
        if(mp.empty())
        {
            int  j = pointerr2;
            while(j <= n)
            {
                if(frnt[j].p == frnt[pointerr2].p)
                {
                    mp.insert({frnt[j].h , frnt[j].idx});
                    j++;
                }
                else
                    break;
            }
            pointerr2 = j;
        }

        pair <int, int> tmp_f = st.top();
        st.pop();

        int val = tmp_f.first;
        auto it = mp.lower_bound({val, 0});

//        for(auto mp_x : mp)
//        {
//            cout << mp_x.first << " -> " << mp_x.second << endl;
//        }
//        cout << " for " << i << endl;
//        cout << "searhinf " << val << " " <<(*it).first<<endl;
        if(it == mp.begin())
        {
            f = 1;
            break;
        }
        it--;
//        cout << "searhinf " << val << " " <<(*it).first<<endl;
        if((*it).second >= val)
            assert(0);
        ans1.push_back(tmp_f.second);
        ans2.push_back((*it).second);
        mp.erase(it);

    }
    if(f)
    {
        cout << "impossible" << endl;
    }
    else
    {
        for(auto x : ans1)
        {
            cout << x << " ";
        }
        cout << endl;
        for(auto x : ans2)
        {
            cout << x << " ";
        }
        cout << endl;
    }

}


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;
}

Details

Test #1:

score: 0
Dangerous Syscalls