QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#60113#2337. AzulejoscapturedAC ✓545ms41816kbC++174.5kb2022-11-02 21:35:232022-11-02 21:35:25

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:35:25]
  • Judged
  • Verdict: AC
  • Time: 545ms
  • Memory: 41816kb
  • [2022-11-02 21:35:23]
  • 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;
    }
    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()
//            }
//        }
//    }
    queue<pair<int, int > >st;
    int pointerr = 1;
    int pointerr2 = 1;
    multiset <pair <int, int> >mp, mp2;
    vector<int> ans1 ,ans2;
    for(int  i  = 1; i <= n; i++)
    {
        if(mp2.empty())
        {
            int  j = pointerr;
            while(j <= n)
            {
                if(bck[j].p == bck[pointerr].p)
                {
                    mp2.insert({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;
        }

        auto tmp_f = mp2.begin();

        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())
        {
            auto tmp_f2 = mp.begin();

            val = (*tmp_f2).first;
            auto it2 = mp2.upper_bound({val, 1e9+7});

    //        for(auto mp_x : mp)
    //        {
    //            cout << mp_x.first << " -> " << mp_x.second << endl;
    //        }
    //        cout << " for " << i << endl;
    //        cout << "searhinf " << val << " " <<(*it).first<<endl;
            if(it2 == mp2.end())
            {
                f = 1;
                break;
            }
    //        cout << "searhinf " << val << " " <<(*it).first<<endl;

            ans2.push_back((*tmp_f2).second);
            ans1.push_back((*it2).second);
            mp2.erase(it2);
            mp.erase(mp.begin());
        }
        else {
            it--;
//        cout << "searhinf " << val << " " <<(*it).first<<endl;
            if((*it).first >= val)
                assert(0);
            ans1.push_back((*tmp_f).second);
            ans2.push_back((*it).second);
            mp.erase(it);
            mp2.erase(mp2.begin());
        }

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

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 7668kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

score: 0
Accepted
time: 75ms
memory: 12500kb

Test #23:

score: 0
Accepted
time: 71ms
memory: 16164kb

Test #24:

score: 0
Accepted
time: 92ms
memory: 15944kb

Test #25:

score: 0
Accepted
time: 55ms
memory: 12376kb

Test #26:

score: 0
Accepted
time: 334ms
memory: 40376kb

Test #27:

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

Test #28:

score: 0
Accepted
time: 82ms
memory: 16528kb

Test #29:

score: 0
Accepted
time: 68ms
memory: 16396kb

Test #30:

score: 0
Accepted
time: 46ms
memory: 16448kb

Test #31:

score: 0
Accepted
time: 545ms
memory: 41816kb

Test #32:

score: 0
Accepted
time: 93ms
memory: 16452kb

Test #33:

score: 0
Accepted
time: 454ms
memory: 40224kb