QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379801#2337. Azulejosdistant_yesterday#AC ✓399ms73632kbC++204.2kb2024-04-06 19:11:342024-04-06 19:11:35

Judging History

This is the latest submission verdict.

  • [2024-04-06 19:11:35]
  • Judged
  • Verdict: AC
  • Time: 399ms
  • Memory: 73632kb
  • [2024-04-06 19:11:34]
  • Submitted

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include "cp_debug.h"
#else
#define debug(...) 42
#endif
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}
template<typename T> void write(T x) {
    if(x > 9) write(x/10);
    putchar(x%10 + '0');
}

vector<vector<pii>> get_groups(vector<tuple<int,int,int>> a) {
    int last_price = -1;
    vector<pii> last_group;
    vector<vector<pii>> ans;
    debug(a);
    for(auto [price, height, idx]: a){
        if(price != last_price) {
            if(sz(last_group) > 0) {
                ans.emplace_back(last_group);
                last_group.clear();
            }
            last_price = price;
        }
        last_group.emplace_back(height, idx);
    }
    if(sz(last_group) > 0) {
        ans.emplace_back(last_group);
    }
    return ans;
}

const int INF = 0x3f3f3f3f;
void solve() {
    int n;
    read(n);
    vector<tuple<int,int,int>> front(n), back(n);
    rep(i,0,n) read(get<0>(back[i]));
    rep(i,0,n) read(get<1>(back[i]));
    rep(i,0,n) read(get<0>(front[i]));
    rep(i,0,n) read(get<1>(front[i]));
    rep(i,0,n) {
        get<2>(back[i])=i;
        get<2>(front[i])=i;
    }
    sort(all(front));
    sort(all(back));

    vector<vector<pii>> back_groups = get_groups(back);
    vector<vector<pii>> front_groups = get_groups(front);

    debug(back_groups);
    debug(front_groups);

    vi ans_front(n, -1), ans_back(n, -1);
    set<pii> cfront, cback;
    int completed = 0, fg_id = 0, bg_id = 0;
    while(completed < n) {
        if(cfront.empty()) {
            assert(fg_id < sz(front_groups));
            for(auto p: front_groups[fg_id]) {
                cfront.insert(p);
            }
            fg_id++;
        }
        if(cback.empty()) {
            assert(bg_id < sz(back_groups));
            for(auto p: back_groups[bg_id]) {
                cback.insert(p);
            }
            bg_id++;
        }
        debug(cfront, cback);
        if(sz(cfront) <= sz(cback)) {
            while(cfront.size()) {
                debug("1",completed,cfront, cback);
                auto [val, pos] = *cfront.begin();
                cfront.erase(cfront.begin());
                auto it = cback.upper_bound({val, INF});
                if(it == cback.end()) {
                    debug(val,pos,"GG");
                    cout<<"impossible"<<'\n';
                    return;
                } else {
                    debug(val,pos,"matched", it->first,it->second);
                    ans_front[completed] = pos;
                    ans_back[completed] = it->second;
                    assert(it->first > val);
                    cback.erase(it);
                    completed++;
                }
            }
        } else {
            while(cback.size()) {
                debug("2",completed,cfront, cback);
                auto [val, pos] = *cback.begin();
                cback.erase(cback.begin());
                auto it = cfront.lower_bound({val, -INF});
                if(it == cfront.begin()) {
                    debug(val,pos,"cannot go before begin");
                    cout<<"impossible"<<'\n';
                    return;
                }
                --it;
                debug(val,pos,"matcheD", it->first,it->second);
                ans_front[completed] = it->second;
                ans_back[completed] = pos;
                assert(val > it->first);
                cfront.erase(it);
                completed++;
            }
        }
    }
    rep(i,0,n) cout<<(ans_back[i]+1)<<" \n"[i==n-1];
    rep(i,0,n) cout<<(ans_front[i]+1)<<" \n"[i==n-1];
}

signed main() {
    int T; T = 1;
    while(T--) solve();
    return 0;
}

Details

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 0
Accepted
time: 241ms
memory: 73632kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

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

Test #23:

score: 0
Accepted
time: 35ms
memory: 11296kb

Test #24:

score: 0
Accepted
time: 54ms
memory: 11188kb

Test #25:

score: 0
Accepted
time: 42ms
memory: 10336kb

Test #26:

score: 0
Accepted
time: 184ms
memory: 73272kb

Test #27:

score: 0
Accepted
time: 37ms
memory: 17044kb

Test #28:

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

Test #29:

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

Test #30:

score: 0
Accepted
time: 30ms
memory: 17164kb

Test #31:

score: 0
Accepted
time: 399ms
memory: 73376kb

Test #32:

score: 0
Accepted
time: 57ms
memory: 17356kb

Test #33:

score: 0
Accepted
time: 303ms
memory: 73280kb