QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#389837#2337. Azulejosneal2022AC ✓888ms108084kbC++231.5kb2024-04-14 20:16:132024-04-14 20:16:13

Judging History

This is the latest submission verdict.

  • [2024-04-14 20:16:13]
  • Judged
  • Verdict: AC
  • Time: 888ms
  • Memory: 108084kb
  • [2024-04-14 20:16:13]
  • Submitted

answer

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

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  std::cin >> n;

  auto get = [&]() {
    std::map<int, std::set<std::array<int, 2>>> a;
    std::vector<int> xs(n), ys(n);
    for (auto& x : xs) std::cin >> x;
    for (auto& y : ys) std::cin >> y;
    for (int i = 0; i < n; i++) {
      a[xs[i]].insert({ys[i], i});
    }
    return a;
  };

  auto a = get();
  auto b = get();

  std::vector<int> a_order, b_order;
  while (a.size() && b.size()) {
    auto& a_first = a.begin()->second;
    auto& b_first = b.begin()->second;
    if (a_first.size() >= b_first.size()) {
      for (auto& [h, bi] : b_first) {
        b_order.push_back(bi);
        auto a_it = a_first.upper_bound({h, n});
        if (a_it == a_first.end()) {
          std::cout << "impossible\n";
          return 0;
        }
        a_order.push_back((*a_it)[1]);
        a_first.erase(a_it);
      }
      b.erase(b.begin());
    } else {
      for (auto& [h, ai] : a_first) {
        a_order.push_back(ai);
        auto b_it = b_first.upper_bound({h, -1});
        if (b_it == b_first.begin()) {
          std::cout << "impossible\n";
          return 0;
        }
        b_it--;
        b_order.push_back((*b_it)[1]);
        b_first.erase(b_it);
      }
      a.erase(a.begin());
    }
  }
  for (auto& x : a_order) std::cout << x + 1 << " ";
  std::cout << "\n";
  for (auto& x : b_order) std::cout << x + 1 << " ";
  std::cout << "\n";
}


Details

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 0
Accepted
time: 356ms
memory: 101248kb

Test #13:

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

Test #14:

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

Test #15:

score: 0
Accepted
time: 6ms
memory: 5236kb

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

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

Test #23:

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

Test #24:

score: 0
Accepted
time: 81ms
memory: 14432kb

Test #25:

score: 0
Accepted
time: 56ms
memory: 18244kb

Test #26:

score: 0
Accepted
time: 320ms
memory: 101416kb

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

score: 0
Accepted
time: 52ms
memory: 23120kb

Test #31:

score: 0
Accepted
time: 888ms
memory: 106128kb

Test #32:

score: 0
Accepted
time: 104ms
memory: 23652kb

Test #33:

score: 0
Accepted
time: 655ms
memory: 108084kb