QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#53573#2337. Azulejosnot_so_organicAC ✓685ms50664kbC++112.4kb2022-10-05 13:32:192022-10-05 13:32:21

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-10-05 13:32:21]
  • Judged
  • Verdict: AC
  • Time: 685ms
  • Memory: 50664kb
  • [2022-10-05 13:32:19]
  • Submitted

answer

#include <bits/stdc++.h>
#define N 500005
#define Ms(a,b) memset(a,b,sizeof a)
#define db(x) cerr<<#x<<"="<<x<<endl;
#define db2(x,y) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define db3(x,y,z) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
using namespace std;
int rd() {
    int res = 0, c;

    while (c = getchar(), c < 48);

    do
        res = (res << 1) + (res << 3) + (c ^ 48);

    while (c = getchar(), c >= 48);

    return res;
}
struct node {
    int x, v, h;
    bool operator <(const node &b)const {
        return h < b.h;
    }
} a[N], b[N];
struct cmp {
    bool operator()(const node &a, const node &b)const {
        return a.v < b.v;
    }
};
int n, r1[N], r2[N];
multiset<node>st1, st2;
multiset<node>::iterator it, cur;
int main() {
    n = rd();

    for (int i = 1; i <= n; i++)
        a[i].v = rd();

    for (int i = 1; i <= n; i++)
        a[i].h = rd(), a[i].x = i;

    for (int i = 1; i <= n; i++)
        b[i].v = rd();

    for (int i = 1; i <= n; i++)
        b[i].h = rd(), b[i].x = i;

    sort(a + 1, a + 1 + n, cmp());
    sort(b + 1, b + 1 + n, cmp());
    int s = 1, t1 = 0, t2 = 0;

    while (s <= n) {
        if (t1 < s) {
            st1.insert(a[s]), t1 = s;

            while (t1 < n && a[t1].v == a[t1 + 1].v)
                st1.insert(a[++t1]);
        }

        if (t2 < s) {
            st2.insert(b[s]), t2 = s;

            while (t2 < n && b[t2].v == b[t2 + 1].v)
                st2.insert(b[++t2]);
        }

        if (t1 <= t2) {
            for (cur = st1.begin(); cur != st1.end(); cur++) {
                it = st2.lower_bound(*cur);

                if (it == st2.begin())
                    return puts("impossible"), 0;
                else
                    it--;

                r1[s] = cur->x, r2[s] = it->x, ++s;
                st2.erase(it);
            }

            st1.clear();
        } else {
            for (cur = st2.begin(); cur != st2.end(); cur++) {
                it = st1.upper_bound(*cur);

                if (it == st1.end())
                    return puts("impossible"), 0;

                r1[s] = it->x, r2[s] = cur->x, ++s;
                st1.erase(it);
            }

            st2.clear();
        }
    }

    for (int i = 1; i <= n; i++)
        printf("%d%c", r1[i], " \n"[i == n]);

    for (int i = 1; i <= n; i++)
        printf("%d%c", r2[i], " \n"[i == n]);

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 5764kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 0
Accepted
time: 275ms
memory: 50664kb

Test #13:

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

Test #14:

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

Test #15:

score: 0
Accepted
time: 8ms
memory: 6508kb

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

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

Test #23:

score: 0
Accepted
time: 74ms
memory: 13136kb

Test #24:

score: 0
Accepted
time: 84ms
memory: 12604kb

Test #25:

score: 0
Accepted
time: 50ms
memory: 7656kb

Test #26:

score: 0
Accepted
time: 144ms
memory: 50324kb

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

score: 0
Accepted
time: 36ms
memory: 14608kb

Test #31:

score: 0
Accepted
time: 685ms
memory: 50592kb

Test #32:

score: 0
Accepted
time: 70ms
memory: 14588kb

Test #33:

score: 0
Accepted
time: 576ms
memory: 50520kb