QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#578725 | #9284. Christmas Children Circle | sea_bird | WA | 3ms | 27844kb | C++20 | 1.9kb | 2024-09-20 21:00:35 | 2024-09-20 21:00:36 |
Judging History
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) {
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;
if (mp[nxt][v] > 0) {
que.push({nxt, v});
}
}
std::vector<pii>qp;
for (int i = 1; i <= n; i++) {
if (give[i])
continue;
qp.push_back({mp[i].size(), i});
}
std::sort(qp.begin(), qp.end());
for (auto [siz, u] : qp) {
int nxt = u % n + 1;
for (auto [x, v] : mp[u]) {
if (mp[nxt][x] <= 0 and v > 0) {
give[u] = x;
break;
}
}
}
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: 0ms
memory: 27844kb
input:
3 2 1 4 2 4 3 2 3 1
output:
1 4 3
result:
ok Participant's answer is valid
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 27048kb
input:
4 1 2 1 3 1 5 1 2
output:
2 3 5 0
result:
wrong answer x[3]=0 does not belong to a[3]