QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#578646#9284. Christmas Children Circlesea_birdWA 3ms28412kbC++202.0kb2024-09-20 20:37:562024-09-20 20:37:56

Judging History

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

  • [2024-09-20 20:37:56]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:28412kb
  • [2024-09-20 20:37:56]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
const int maxn = 5e5 + 100;
std::map<int, int>mp[maxn];
std::vector<int>arr[maxn];
int give[maxn];
void solve() {
    int n;
    std::cin >> n;
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        int siz;
        std::cin >> siz;
        for (int j = 1; j <= siz; j++) {
            int x;
            std::cin >> x;
            mp[i][x]++;
            if (mp[i][x] == 2) {
                arr[i].push_back(x);
            }
            if (arr[i].size() > 1 or mp[i][x] > 2)
                flag = false;
        }
    }
    if (!flag) {
        std::cout << "-1\n";
        return;
    }
    std::queue<pii>que;
    for (int i = 1; i <= n; i++) {
        for (auto x : arr[i]) {
            if (mp[i][x] > 1) {
                mp[i][x]--;
                que.push({i, x});
                break;
            }
        }
    }
    while (!que.empty()) {
        auto [u, v] = que.front();
        que.pop();
        if (give[u]) {
            std::cout << "-1\n";
            return;
        }
        give[u] = v;
        int nxt = u % n + 1;
        mp[nxt][v]++;
        if (mp[nxt][v] > 1) {
            arr[nxt].push_back(v);
        }
        for (auto x : arr[nxt]) {
            if (mp[nxt][x] > 1) {
                mp[nxt][x]--;
                que.push({nxt, x});
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (give[i])
            continue;
        int nxt = i % n + 1;
        for (auto [x, v] : mp[i]) {
            if (mp[nxt][x] <= 0 and v > 0) {
                give[i] = x;
                break;
            }
        }
        mp[nxt][give[i]]++;
        mp[i][give[i]]--;
    }
    for (int i = 1; i <= n; i++) {
        std::cout << give[i] << " \n"[i == n];
    }
}
int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);
    int t = 1;
    while (t--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 28240kb

input:

3
2 1 4
2 4 3
2 3 1

output:

1 4 1

result:

ok Participant's answer is valid

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 28412kb

input:

4
1 2
1 3
1 5
1 2

output:

2 2 5 2

result:

wrong answer x[1]=2 does not belong to a[1]