Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- void solve() {
- int n, m; cin >> n >> m;
- vector<int> ifless(n, 1), ifmore(n, 1);
- // ifless - если меньше остальных, ifmore - если больше остальных. Изначально все могут быть и теми, и теми.
- for (int j = 0; j < m; ++j) {
- int q; cin >> q;
- vector<int> cnt(n, 0);
- // считываем сколько раз он на левой чаше сравнения (отрицательное число значит, что он на противоположной), здесь также учитывается возможность того, что какой-то человек в сравнении участвует несколько раз
- for (int i = 0; i < q; ++i) {
- int a; cin >> a; a--;
- cnt[a]++;
- }
- // сначала добавляем тех, что слева
- for (int i = 0; i < q; ++i) {
- int a; cin >> a; a--;
- cnt[a]--;
- }
- // затем вычитаем тех что справа
- char res; cin >> res;
- // теперь считываем знак
- if (res == '=') {
- for (int i = 0; i < n; ++i) {
- if (cnt[i] != 0) {
- ifless[i] = 0; ifmore[i] = 0;
- }
- }
- }
- // если равенство, то это значит, что все, у кого по итогу ненулевой вклад равны, а значит больше не могут быть особенными
- else if (res == '>') {
- for (int i = 0; i < n; ++i) {
- if (cnt[i] <= 0) { ifmore[i] = 0; }
- if (cnt[i] >= 0) { ifless[i] = 0; }
- }
- }
- // если больше, то если у кого-то вклад не больше нуля, то его не может быть слева, а значит он не может весить больше, так как слева уже есть человек, который весит больше. По аналогии с меньше и правой частью
- else {
- for (int i = 0; i < n; ++i) {
- if (cnt[i] >= 0) { ifmore[i] = 0; }
- if (cnt[i] <= 0) { ifless[i] = 0; }
- }
- }
- // точно также, но для случая с противоположным знаком просто меняются и знаки сравнения с нулем
- }
- int ans = 0;
- // ищем ответ. Если у нас есть несколько вариантов того, что кто-то может весить больше остальных (или меньше), то ответ сразу 0, так как мы по итогу не сможем отличить эти варианты. Если же какой-то человек одновременно может весить и больше, и меньше, то это ок, ведь его могли просто ни разу не брать, а все остальные были равны.
- for (int i = 0; i < n; ++i) {
- if (ifless[i]) {
- if (ans == 0) ans = i + 1;
- else {
- cout << "0\n";
- return;
- }
- }
- if (ifmore[i]) {
- if (ans == 0 || ans == i + 1) ans = i + 1;
- else {
- cout << "0\n";
- return;
- }
- }
- }
- cout << ans << endl;
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment