QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#733148#7738. Equivalent Rewritingenar#WA 0ms3816kbC++202.1kb2024-11-10 17:26:102024-11-10 17:26:11

Judging History

你现在查看的是最新测评结果

  • [2024-11-10 17:26:11]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3816kb
  • [2024-11-10 17:26:10]
  • 提交

answer

#include <bits/stdc++.h>

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::set<int> num;
    std::vector<int> cnt(m + 1);
    std::vector<std::set<int>> p(n);
    for (int i = 0; i < n; ++i) {
        int l;
        std::cin >> l;
        for (int j = 0; j < l; ++j) {
            int x;
            std::cin >> x;
            p[i].insert(x);
            num.insert(x);
            cnt[x]++;
        }
    }
    std::vector<int> ans(n);
    std::iota(ans.begin(), ans.end(), 1);
    for (int i = 1; i < n; ++i) {
        bool flag = false;
        for (const auto &u : p[i - 1]) {
            if (p[i].contains(u)) {
                flag = true;
            }
        }
        if (!flag) {
            std::cout << "Yes\n";
            std::swap(ans[i], ans[i - 1]);
            for (int j = 0; j < n; ++j) {
                std::cout << ans[j] << " \n"[j == n - 1];
            }
            return;
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (cnt[i] == 1) {
            num.erase(i);
        }
    }
    std::vector<int> ctn;
    std::vector<int> vis(n);
    for (int i = n - 1; i >= 0; --i) {
        for (const auto &u : p[i]) {
            if (num.contains(u)) {
                if (!vis[i]) ctn.push_back(i);
                num.erase(u);
                vis[i] = true;
            }
        }
        if (num.size() == 0) {
            if (n - ctn.size() >= 2) {
                std::cout << "Yes\n";
                for (int j = n - 1; j >= 0; --j) {
                    if (!vis[j]) {
                        std::cout << j + 1 << " ";
                    }
                }
                for (const auto &u : ctn) {
                    std::cout << u + 1 << " ";
                }
                std::cout << "\n";
                return;
            }
            break;
        }
    }
    std::cout << "No\n";
}

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

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

详细

Test #1:

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

input:

3
3 6
3 3 1 5
2 5 3
2 2 6
2 3
3 1 3 2
2 3 1
1 3
2 2 1

output:

Yes
1 3 2
No
No

result:

ok OK. (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3528kb

input:

1
10 5
2 2 4
4 1 3 4 2
1 2
3 2 1 4
4 5 2 4 3
3 2 5 4
3 5 4 2
3 1 3 2
5 1 4 2 3 5
1 4

output:

Yes
8 7 6 5 4 3 2 1 10 9 

result:

wrong answer two transactions are not equivalent. (test case 1)