QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#699901 | #7738. Equivalent Rewriting | iliyian | WA | 2ms | 8348kb | C++20 | 1.6kb | 2024-11-02 11:11:24 | 2024-11-02 11:11:25 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
int a[100010], b[100010], cover_last[100010], cover_first[100010], first, second, pos;
std::vector <int> p[100010];
void solve() {
int n, m, k;
std::cin >> n >> m;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for(int i = 1; i<= n; i++)
{
int x;
std::cin >> x;
p[i].resize(x + 2);
// std::cin >> p[i][0]
p[i][0] = x;
for(int j = 1; j <= p[i][0]; j++)
{
std::cin >> p[i][j];
a[p[i][j]] = i;
}
}
for(int i = 1; i<= n; i++)
{
cover_last[i] = 0;
cover_first[i] = n + 1;
}
for(int i = 1; i<= n; i++)
{
for(int j = 1; j <= p[i][0]; j++)
{
if(a[p[i][j]] == i) cover_last[i] = std::max(cover_last[i], b[p[i][j]]);
else cover_first[i] = std::min(cover_first[i], a[p[i][j]]);
b[p[i][j]] = i;
}
}
for(int i = 1; i<= n; i++){a[i] = i;b[i] = 0;}
bool flag = 0;
for(int i = 1; i<= n; i++)
{
for(int j = cover_last[i] + 1; j < cover_first[i]; j++)
if(b[j])
{
flag = 1;
pos = j;
second = i;
break;
}
else b[j] = i;
}
if(flag)
{
std::cout << "Yes\n";
for(int i = 1; i <= n; i++)
{
if(i == pos) std::cout << second << ' ';
if(i != second) std::cout << a[i] << ' ';
}
std::cout << std::endl;
}
else
{
std::cout << "No\n";
}
}
signed main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 7220kb
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 3 1 2 No No
result:
ok OK. (3 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 6984kb
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 1 2 3 4 5 6 7 9 10
result:
ok OK. (1 test case)
Test #3:
score: 0
Accepted
time: 1ms
memory: 7232kb
input:
1 20 5 5 4 1 2 5 3 2 5 3 3 5 1 2 5 4 5 1 3 2 3 4 2 5 5 3 1 5 4 2 5 5 1 2 3 4 1 3 4 5 1 2 3 4 4 1 3 5 2 5 2 4 2 3 5 1 3 2 4 5 5 2 3 4 1 5 4 5 2 4 3 1 2 2 4 3 4 4 5 3 1 5 4 1 5 3 2 3 5 1 3
output:
Yes 18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 20
result:
ok OK. (1 test case)
Test #4:
score: 0
Accepted
time: 1ms
memory: 8300kb
input:
1 40 10 2 4 1 10 5 8 2 3 6 7 4 1 10 9 3 10 9 7 1 9 10 10 5 6 9 2 8 3 1 4 7 7 8 4 7 5 2 3 6 5 2 6 5 1 10 6 6 5 4 8 7 1 3 4 9 8 9 9 10 4 2 1 8 7 5 3 2 5 7 9 8 6 1 2 9 7 5 10 3 2 8 1 8 8 3 10 9 1 4 5 6 2 3 4 5 5 3 6 2 7 10 3 2 8 9 10 1 7 4 6 5 2 1 9 1 1 3 3 7 4 5 2 6 5 7 1 7 3 2 4 9 10 6 1 1 4 5 6 4 5 ...
output:
Yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 39 35 36 37 38 40
result:
ok OK. (1 test case)
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 8348kb
input:
1 100 20 12 10 5 11 13 12 14 7 15 19 18 3 1 10 16 11 19 8 10 15 5 12 13 14 12 16 8 11 15 2 18 14 13 20 4 12 7 10 3 9 1 7 19 6 2 14 8 20 7 17 18 20 3 9 6 10 4 1 4 19 9 13 14 17 16 11 13 8 10 19 18 7 5 20 1 13 10 15 3 2 9 1 17 7 20 13 19 18 16 2 17 9 10 20 19 13 14 16 17 8 12 18 15 5 2 16 14 6 19 1 14...
output:
Yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
result:
wrong answer two transactions are same. (test case 1)