QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#768234#2337. AzulejoswxhtzdyAC ✓652ms42472kbC++202.4kb2024-11-21 03:57:132024-11-21 03:57:13

Judging History

This is the latest submission verdict.

  • [2024-11-21 03:57:13]
  • Judged
  • Verdict: AC
  • Time: 652ms
  • Memory: 42472kb
  • [2024-11-21 03:57:13]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> pa(n);
  for (int i = 0; i < n; i++) {
    cin >> pa[i];
  }
  vector<int> ha(n);
  for (int i = 0; i < n; i++) {
    cin >> ha[i];
  }
  vector<int> pb(n);
  for (int i = 0; i < n; i++) {
    cin >> pb[i];
  }
  vector<int> hb(n);
  for (int i = 0; i < n; i++) {
    cin >> hb[i];
  }
  vector<int> order_a(n);
  iota(order_a.begin(), order_a.end(), 0);
  sort(order_a.begin(), order_a.end(), [&](int i, int j) {
    return pa[i] < pa[j];
  });
  vector<int> order_b(n);
  iota(order_b.begin(), order_b.end(), 0);
  sort(order_b.begin(), order_b.end(), [&](int i, int j) {
    return pb[i] < pb[j];
  });
  vector<int> res_a;
  vector<int> res_b;
  set<pair<int, int>> st_a;
  set<pair<int, int>> st_b;
  int ptr_a = 0;
  int ptr_b = 0;
  while ((!st_a.empty() || ptr_a < n) && (!st_b.empty() || ptr_b < n)) {
    if (st_a.empty()) {
      int id = ptr_a;
      while (ptr_a < n && pa[order_a[ptr_a]] == pa[order_a[id]]) {
        st_a.emplace(ha[order_a[ptr_a]], order_a[ptr_a]);
        ptr_a += 1;
      }
    }
    if (st_b.empty()) {
      int id = ptr_b;
      while (ptr_b < n && pb[order_b[ptr_b]] == pb[order_b[id]]) {
        st_b.emplace(hb[order_b[ptr_b]], order_b[ptr_b]);
        ptr_b += 1;
      }
    }
    if (int(st_a.size()) < int(st_b.size())) {
      for (auto& p : st_a) {
        int h = p.first;
        int id = p.second;
        auto it = st_b.lower_bound({h, -1});
        if (it == st_b.begin()) {
          break;
        }
        it = prev(it);
        res_a.push_back(id);
        res_b.push_back(it->second);
        st_b.erase(it);
      }
      st_a.clear();
    } else {
      for (auto& p : st_b) {
        int h = p.first;
        int id = p.second;
        auto it = st_a.lower_bound({h + 1, -1});
        if (it == st_a.end()) {
          break;
        }
        res_a.push_back(it->second);
        res_b.push_back(id);
        st_a.erase(it);
      }
      st_b.clear();
    }
  }
  if (int(res_a.size()) != n || int(res_b.size()) != n) {
    cout << "impossible" << '\n';
  } else {
    for (int i = 0; i < n; i++) {
      cout << res_a[i] + 1 << " ";
    }
    cout << '\n';
    for (int i = 0; i < n; i++) {
      cout << res_b[i] + 1 << " ";
    }
    cout << '\n';
  }
  return 0;
}

詳細信息

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 0
Accepted
time: 208ms
memory: 38192kb

Test #13:

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

Test #14:

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

Test #15:

score: 0
Accepted
time: 5ms
memory: 4316kb

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

score: 0
Accepted
time: 58ms
memory: 6644kb

Test #23:

score: 0
Accepted
time: 59ms
memory: 10160kb

Test #24:

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

Test #25:

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

Test #26:

score: 0
Accepted
time: 186ms
memory: 38324kb

Test #27:

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

Test #28:

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

Test #29:

score: 0
Accepted
time: 41ms
memory: 10344kb

Test #30:

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

Test #31:

score: 0
Accepted
time: 652ms
memory: 42472kb

Test #32:

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

Test #33:

score: 0
Accepted
time: 514ms
memory: 42440kb