QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#620132#7738. Equivalent RewritingMoemi_WA 71ms13444kbC++202.1kb2024-10-07 16:45:262024-10-07 16:45:37

Judging History

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

  • [2024-10-07 16:45:37]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:13444kb
  • [2024-10-07 16:45:26]
  • 提交

answer

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <stack>
#include <cstring>
#include <iomanip>
#include <unordered_map>
#include <numeric>
 
#define sc_int(x) scanf("%d", &x)
 
#define x first
#define y second
#define pb push_back

using namespace std;

const int N = 5010, M = 10010, MOD = 1e9 + 7;
const int inf = 1e9;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<string, int> PSI;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;
typedef pair<char, int> PCI;
typedef pair<string, string> PSS;

LL n, m, k;

void solve() 
{
	cin >> n >> m;
	vector<vector<int>> a(n);
	map<vector<int>, vector<int>> mp1;
	for(int i = 0; i < n; i ++)
	{
		cin >> k;
		while(k -- )
		{
			int x;
			cin >> x;
			a[i].pb(x);
		}
		sort(a[i].begin(), a[i].end());
		a[i].erase(unique(a[i].begin(), a[i].end()), a[i].end());
		mp1[a[i]].pb(i);
	}
	
	for(auto [x, y] : mp1)
	{
		if(y.size() > 1)
		{
			cout << "Yes" << endl;
			int t1 = y[0] + 1, t2 = y[1] + 1;
			for(int i = 1; i <= n; i ++) 
			{
				if(i == t1) cout << t2 << " ";
				else if(i == t2) cout << t1 << " ";
				else cout << i << " ";
			}
			cout << endl;
			return;
		}
	}	
	
	map<int, int> mp;
	for(auto t : a[0]) mp[t] = 1;
	for(int i = 1; i < n; i ++)
	{
		int cnt = 0;
		for(auto t : a[i]) 
		{
			if(mp[t]) cnt ++;
			mp[t] = 1;
		}
		if(!cnt) 
		{
			cout << "Yes" << endl;
			cout << i + 1 << " ";
			for(int j = 1; j <= n; j ++) 
			{
				if(j - 1 != i) cout << j << " ";
			}
			cout << endl;
			return;
		}
		else if(cnt == mp.size())
		{
			cout << "Yes" << endl;
			cout << 2 << " " << 1 << " ";
			for(int j = 3; j <= n; j ++)
			{
				cout << j << " ";
			}
			cout << endl;
			return;
		}
	}
	cout << "No" << endl;
}


int main()
{
//  freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
     
    int T = 1;
    cin >> T;
    while(T --)
    {
        solve();
    }
}

详细

Test #1:

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

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: 3560kb

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
1 2 3 4 5 7 6 8 9 10 

result:

ok OK. (1 test case)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3548kb

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
4 2 3 1 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

result:

ok OK. (1 test case)

Test #4:

score: 0
Accepted
time: 0ms
memory: 3596kb

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 5 3 4 2 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 

result:

ok OK. (1 test case)

Test #5:

score: 0
Accepted
time: 0ms
memory: 3580kb

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 53 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 18 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:

ok OK. (1 test case)

Test #6:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

1
5000 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1...

output:

Yes
2 1 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 101 ...

result:

ok OK. (1 test case)

Test #7:

score: 0
Accepted
time: 31ms
memory: 9432kb

input:

1
5000 200
2 121 161
35 27 5 1 189 173 2 37 107 140 172 108 53 163 19 127 102 174 71 178 42 72 74 167 118 120 175 28 75 128 106 190 112 86 171 13
109 110 109 183 17 77 159 188 157 56 14 104 55 179 121 171 64 123 196 140 38 29 134 130 163 108 187 42 68 26 156 138 80 143 182 4 174 67 63 76 79 69 142 3...

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 101 ...

result:

ok OK. (1 test case)

Test #8:

score: 0
Accepted
time: 67ms
memory: 13444kb

input:

1
5000 1000
146 147 426 393 758 104 385 277 218 753 477 377 54 465 635 918 97 453 576 270 57 189 230 227 332 345 358 14 178 969 817 840 620 828 837 94 922 844 789 106 250 952 745 212 693 296 677 368 625 150 103 55 266 756 525 60 91 683 364 852 877 792 312 315 997 27 50 866 759 327 557 56 49 947 644 ...

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 101 ...

result:

ok OK. (1 test case)

Test #9:

score: -100
Wrong Answer
time: 71ms
memory: 13388kb

input:

1
4999 1000
799 991 88 253 814 577 620 74 338 485 560 435 835 130 279 536 637 188 612 876 634 950 755 534 727 272 657 357 810 113 800 41 439 125 763 311 724 623 976 525 725 869 209 975 888 683 428 4 91 448 936 885 140 233 967 556 369 522 263 483 784 96 808 70 42 391 109 333 778 422 121 862 430 746 6...

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 101 ...

result:

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