2019 ICPC World Finals A Azulejos

Descriprion:

Ceramic artists Maria and João are opening a small $\texttt{azulejo}$ store in Porto. $\texttt{Azulejos}$ are the beautiful ceramic tiles for which Portugal is famous. Maria and João want to create an attractive window display, but, due to limited space in their shop, they must arrange their tile samples in two rows on a single shelf. Each of João’s tiles has exactly one of Maria’s tiles in front of it and each of Maria’s tiles has exactly one of João’s tiles behind it. These hand-crafted tiles are of many different sizes, and it is important that each tile in the back row is taller than the tile in front of it so that both are visible to passers-by. For the convenience of shoppers, tiles in each row are arranged in non-decreasing order of price from left to right. Tiles of the same price may be arranged in any order subject to the visibility condition stated above.

Your task is to find an ordering of the tiles in each row that satisfies these constraints, or determine that no such ordering exists.

Input:

The first line of input contains an integer $n$ ($1≤n≤5⋅10^{5}$ ), the number of tiles in each row. The next four lines contain $n$ integers each; the first pair of lines represents the back row of tiles and the second pair of lines represents the front row. Tiles in each row are numbered from $1$ to nn according to their ordering in the input. The first line in each pair contains $n$ integers $p_{1},…,p_{n}$ ($1≤p_{i}≤10^{9}$ for each $i$ ), where $pi$ is the price of tile number $i$ in that row. The second line in each pair contains $n$ integers $h_{1},…,h_{n}$ ($1≤h_{i}≤10^9$ for each $i$ ), where $hi$ is the height of tile number ii in that row.

Output:

If there is a valid ordering, output it as two lines of $n$ integers, each consisting of a permutation of the tile numbers from $1$ to $n$ . The first line represents the ordering of the tiles in the back row and the second represents the ordering of the tiles in the front row. If more than one pair of permutations satisfies the constraints, any such pair will be accepted. If no ordering exists, output impossible.

Sample Input:

4
3 2 1 2
2 3 4 3
2 1 2 1
2 2 1 3

Sample Output:

3 2 4 1
4 2 1 3

Sample Input:

2
1 2
2 3
2 8
2 1

Sample Output:

impossible

题目链接

$\texttt{2019 ICPC World Finals - Porto}$ 的签到题,南京大学咖啡鸡队在 $\texttt{21min}$ 时 $\texttt{1A}$ 了此题并抢到一血,Orz

题意为:两行 $n$ 列瓷砖,求一种排列使得每行瓷砖价格保持非降序,每列瓷砖高度严格递增

一个显然的思路是对每行瓷砖按照价格进行分段,之后枚举行位,找到两行中合适的瓷砖进行填充

这里瓷砖的填充有两种情况

  1. 后排瓷砖此段元素数量大于前排瓷砖此段元素数量

例如:

#123
back{1,4}{1,4}{2,6}
front{1,3}{1,3}{1,3}

这里后排分为两段 {1,4}、{1,4}{2,6} ,前排只有一段 {1,3}、{1,3}、{1,3} ,所以根据后排(段大小较小的行)进行填充,先在后排此位置填充 {1,4} ,之后在前排此段内查找高度比 $4$ 小的最大值进行填充

  1. 后排瓷砖此段元素数量小于前排瓷砖此段元素数量

例如:

#123
back{1,5}{1,4}{1,3}
front{1,2}{1,3}{2,4}

这里前排分为两段 {1,2}、{1,3}{2,4} ,后排只有一段 {1,5}、{1,4}、{1,3} ,所以根据前排(段大小较小的行)进行填充,现在前排填充 {1,2} ,之后在后排此段内查找高度比 $2$ 大的最小值进行填充

后排瓷砖此段元素数量等于前排瓷砖此段元素数量时可以分到两种情况中的任意一种

我最开始使用 $\texttt{std::vector}$ 容器进行的分段,分段之后排序在查找时进行二分查找,但可能排序次数较多所以一直 $\texttt{TLE}$ ,之后看 $\texttt{tourist}$ 大神直播发现他利用 $\texttt{std::set}$ 进行分段、排序、查找实现,复杂度会降低很多,感觉用码量极大的伸展树也可以实现这些操作,不知道有没有人这么做(大雾

AC代码:

#include <bits/stdc++.h>

struct tile {int p, h, id;};
bool operator < (tile k1, tile k2) {
  if (k1.h == k2.h) return k1.id < k2.id;
  return k1.h < k2.h;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  int n; std::cin >> n;
  std::vector<tile> b(n), f(n);
  for (int i = 0; i < n; ++i) std::cin >> b[i].p;
  for (int i = 0; i < n; ++i) std::cin >> b[i].h;
  for (int i = 0; i < n; ++i) b[i].id = i;
  for (int i = 0; i < n; ++i) std::cin >> f[i].p;
  for (int i = 0; i < n; ++i) std::cin >> f[i].h;
  for (int i = 0; i < n; ++i) f[i].id = i;

  sort(b.begin(), b.end(), [&](tile k1, tile k2) {return k1.p < k2.p;});
  sort(f.begin(), f.end(), [&](tile k1, tile k2) {return k1.p < k2.p;});

  std::set<tile> b_s, f_s;
  std::vector<int> b_ans(n), f_ans(n);
  int b_cur = 0, f_cur = 0;

  for (int pos = 0; pos < n; ++pos) {
    if (b_s.empty()) {
      while (b_cur < n) {
        b_s.insert(b[b_cur]);
        ++b_cur;
        if (b[b_cur].p != b[b_cur - 1].p) break;
      }
    }
    if (f_s.empty()) {
      while (f_cur < n) {
        f_s.insert(f[f_cur]);
        ++f_cur;
        if (f[f_cur].p != f[f_cur - 1].p) break;
      }
    }
    
    if ((int)b_s.size() < (int)f_s.size()) {
      tile b_tmp = *b_s.begin();
      b_s.erase(b_s.begin());
      b_ans[pos] = b_tmp.id;
      auto it = f_s.lower_bound((tile){-1, b_tmp.h, -1});
      if (it == f_s.begin()) {
        std::cout << "impossible" << '\n';
        return 0;
      }
      tile f_tmp = *std::prev(it);
      f_ans[pos] = f_tmp.id;
      f_s.erase(std::prev(it));
    }
    else {
      tile f_tmp = *f_s.begin();
      f_s.erase(f_s.begin());
      f_ans[pos] = f_tmp.id;
      auto it = b_s.lower_bound((tile){-1, f_tmp.h + 1, -1});
      if (it == b_s.end()) {
        std::cout << "impossible" << '\n';
        return 0;
      }
      tile b_tmp = *it;
      b_ans[pos] = b_tmp.id;
      b_s.erase(it);
    }
  }

  for (auto &v : b_ans) std::cout << v + 1 << " ";
  std::cout << '\n';
  for (auto &v : f_ans) std::cout << v + 1 << " ";
  std::cout << '\n';
  return 0;
}
Last modification:April 5th, 2019 at 01:41 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment