1408 . 宗教戰爭（除蟲題）
TopCoder
Tags
Description
在程式競賽的圈子中，處處可見所謂的「宗教戰爭」，像是區間應該要用左閉右閉還是左閉右開、大括號要不要下放、要用 lambda expression 還是全域 function 等等，都是競賽選手們爭論不休、各執己見，又永遠得不到共識的話題。
你寫你的 suffix array，他用他的 suffix automaton，彼此都會有可用的後綴結構。尊重每個人的喜好是很重要的事情，買水果也是一樣，有些人覺得甜的水果比較好吃、有些人覺得酸的水果比較好吃，也有的人覺得像榴槤這種有獨特氣味與口感的水果很好吃。為了滿足有不同喜好的客人的需求，艾文線上水果商店最近推出了新功能，來讓有不同喜好的人都能馬上找到自己最喜歡的水果。
艾文線上水果商店很特別，販賣的每一種水果都獨一無二，只有一顆，賣掉就沒有了，而且還會不定時出現新的水果。在艾文線上水果商店中，水果專家會為每顆水果的某 $M$ 種特定性質（例如甜度、酸度等等）評分，並記錄為 $M$ 個數字，這樣客人就可以根據這 $M$ 種性質的評分結果，來決定他要買哪一顆水果。
因為有很多客戶的喜好都很相近，所以水果專家們還會根據巿場需求整理出常見的「水果喜好」，一個「水果喜好」以一個序列 $p_1,p_2,\dots,p_M$ 表示，其中 $|p_1|,|p_2|,\dots,|p_M|$ 是一個 $1 \sim M$ 的 permutation。意思是對於一個有著這個喜好的客人來說，如果他要在兩顆性質評分分別為 $a_1,a_2,\dots,a_M$ 和 $b_1,b_2,\dots,b_M$ 的水果之間選擇一顆他比較喜歡的，那麼首先他會先找到最小的整數 $i \in [1, M]$ 滿足 $a_{|p_i|} \neq b_{|p_i|}$，並且
- 如果 $p_i > 0$，這名客人會選擇第 $p_i$ 個性質的評分較大的水果。
- 如果 $p_i < 0$，這名客人會選擇第 $p_i$ 個性質的評分較小的水果。
簡單來說，$|p_1|,|p_2|,\dots,|p_M|$ 就是這名客人在乎的性質的優先順序，而 $p_i$ 的正負號代表這名客人認為第 $p_i$ 個性質是分數越大越好還是越小越好。
艾文線上水果商店的工程師寫了一個程式來處理以下三種事件：
- $1\ a_1\ a_2\ \dots\ a_M$：有一顆新進貨的水果，性質評分是 $a_1,a_2,\dots,a_M$，這顆水果會馬上被放到貨架上。第 $i$ 顆被放到貨架上的水果編號為 $i$。一開始貨架是空的。
- $2\ p_1\ p_2\ \dots\ p_M$：水果專家們新增了一種常見水果喜好 $p_1,p_2,\dots,p_M$。第 $i$ 個新增的水果喜好編號為 $i$。
- $3\ x$：有一個有著編號為 $x$ 的水果喜好的客人要買水果，他買走了根據喜好的定義，他最喜歡的水果。如果有一堆性質完全一樣的水果，都是他最喜歡的水果的話，那麼他會選擇其中編號最小的水果。他買走水果之後，這顆水果就會永遠從貨架上消失（注意他的編號會變成空號，不會有別的水果遞補）。
然而，他們很快就收到使用者的抱怨，說這個系統總是在推薦一些他們一點都不喜歡的水果！請幫他們在 edit distance
- 3 (40 Points)
- 2 (60 Points)
以內將程式碼修改正確，免得被艾文老闆開除。
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int m, q;
cin >> m >> q;
vector<vector<int>> a(1);
auto make_comp = [&](vector<int> &o) {
return [&](int x, int y) {
for (int i : o) {
int sign = clamp(i, -1, 1);
i = abs(i);
if (a[x][i] != a[y][i])
return sign == 1 ? a[x][i] < a[y][i] : a[x][i] > a[y][i];
}
return x > y;
};
};
vector<int> ord(m);
using PQ = priority_queue<int, vector<int>, decltype(make_comp(ord))>;
vector<PQ> pqs;
pqs.emplace_back(PQ(make_comp(ord)));
vector<bool> sold(1);
while (q--) {
int op;
cin >> op;
if (op == 1) {
int id = a.size();
a.emplace_back(vector<int>(m + 1));
for (int i = 1; i <= m; i++) cin >> a.back()[i];
sold.emplace_back(false);
for (int i = 1; i < pqs.size(); i++)
pqs[i].push(id);
}
else if (op == 2) {
for (int i = 0; i < m; i++) cin >> ord[i];
pqs.emplace_back(PQ(make_comp(ord)));
for (int i = 1; i < a.size(); i++)
pqs.back().push(i);
}
else if (op == 3) {
int favor;
cin >> favor;
while (!pqs[favor].empty() && sold[pqs[favor].top()])
pqs[favor].pop();
if (pqs[favor].empty()) cout << "QAQ\n";
else {
cout << pqs[favor].top() << "\n";
sold[pqs[favor].top()] = true;
pqs[favor].pop();
}
}
}
}
Input Format
第一行有兩個整數 $M,Q$，代表水果專家們評分的性質數量，以及有幾個事件。
接下來有 $Q$ 行，其中第 $i$ 行代表第 $i$ 個事件的資訊，格式為以下其中之一：
- $1\ a_1\ a_2\ \dots\ a_M$
- $2\ p_1\ p_2\ \dots\ p_M$
- $3\ x$
意義如題目敘述所述。
- $1 \leq M,Q \leq 300$（看來艾文線上水果商店的生意不是很好）
- 第一種事件中，$-10^ 9 \leq a_i \leq 10^ 9$
- 第二種事件中，$1 \leq |p_i| \leq M$、$|p_1|,|p_2|,\dots,|p_M|$ 是 $1 \sim M$ 的 permutation
- 第三種事件中，$x \geq 1$ 且 $x \leq$ 已有的第二種事件總數
Output Format
對於每個第三種事件，如果貨架上已經沒有水果了，輸出 QAQ，否則輸出該客人會買走的水果編號。
Sample Input 1
3 8 1 1 2 3 1 2 1 3 1 3 2 1 2 2 1 3 2 3 -1 -2 3 1 3 2 3 1
Sample Output 1
3 1 2
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~14 | 無額外限制 | 100 |