QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#578646 | #9284. Christmas Children Circle | sea_bird | WA | 3ms | 28412kb | C++20 | 2.0kb | 2024-09-20 20:37:56 | 2024-09-20 20:37:56 |
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) {
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;
}
详细
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]