QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#641087	#6109. Similarity Graph	cxm1024	TL	197ms	3732kb	C++17	1.7kb	2024-10-14 18:24:34	2024-10-14 18:24:35

Judging History

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

[2024-10-14 18:24:35]
评测

测评结果：TL
用时：197ms
内存：3732kb

查看

[2024-10-14 18:24:34]
提交

answer

#include <bits/stdc++.h>
#define cerr cout << "in " << __LINE__ << "\t: "
using namespace std;
int n, m, a[110][110], p[110], q[110], b[110][110], ans[110];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n, m = n, iota(q + 1, q + n + 1, 1);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> a[i][j];
	if (n <= 7) {
		for (int i = 1; i <= n; i++)
			p[i] = q[i] = i;
		do {
			do {
				bool flag = 1;
				for (int i = 1; i <= n; i++)
					for (int j = 1; j <= n; j++)
						if (i != j && a[i][j] != ((p[i] < p[j]) == (q[i] < q[j])))
							flag = 0;
				if (flag) {
					cout << "YES\n";
					for (int i = 1; i <= n; i++)
						cout << p[i] << " \n"[i == n];
					for (int i = 1; i <= n; i++)
						cout << q[i] << " \n"[i == n];
					return 0;
				}
			} while (next_permutation(q + 1, q + n + 1));
		} while (next_permutation(p + 1, p + n + 1));
		cout << "NO\n";
		return 0;
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			a[i][j] ^= (i > j);
	for (; n; n--) {
		int flag = 0;
		for (int i = 1; i <= n; i++) {
			int res = 0;
			for (int j = 1; j <= n; j++)
				res += a[i][j];
			if (res == n - 1) flag = i;
		}
		if (!flag) {
			cout << "NO\n";
			return 0;
		}
		ans[q[flag]] = n;
		int tot = 0;
		for (int i = 1; i <= n; i++)
			if (i != flag) p[i] = ++tot, q[p[i]] = q[i];
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (i != flag && j != flag) b[p[i]][p[j]] = a[i][j];
		memcpy(a, b, sizeof(b));
	}
	cout << "YES\n";
	for (int i = 1; i <= m; i++)
		cout << i << " \n"[i == m];
	for (int i = 1; i <= m; i++)
		cout << ans[i] << " \n"[i == m];
	return 0;
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3612kb

input:

output:

YES
1 2 3 4
2 4 1 3

result:

ok ok

Test #2:

score: 0

Accepted

time: 22ms

memory: 3672kb

input:

6
0 1 0 1 0 1
1 0 0 0 1 0
0 0 0 1 1 1
1 0 1 0 0 0
0 1 1 0 0 0
1 0 1 0 0 0

output:

NO

result:

ok ok

Test #3:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

1
0

output:

YES
1
1

result:

ok ok

Test #4:

score: 0

Accepted

time: 0ms

memory: 3728kb

input:

2
0 0
0 0

output:

YES
1 2
2 1

result:

ok ok

Test #5:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

2
0 1
1 0

output:

YES
1 2
1 2

result:

ok ok

Test #6:

score: 0

Accepted

time: 0ms

memory: 3660kb

input:

output:

YES
1 2 3
3 2 1

result:

ok ok

Test #7:

score: 0

Accepted

time: 0ms

memory: 3660kb

input:

output:

YES
1 2 3
3 1 2

result:

ok ok

Test #8:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

output:

YES
1 3 2
2 1 3

result:

ok ok

Test #9:

score: 0

Accepted

time: 0ms

memory: 3656kb

input:

output:

YES
1 2 3
2 1 3

result:

ok ok

Test #10:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

output:

YES
1 2 3
2 3 1

result:

ok ok

Test #11:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

output:

YES
1 3 2
2 3 1

result:

ok ok

Test #12:

score: 0

Accepted

time: 0ms

memory: 3664kb

input:

output:

YES
1 2 3
1 3 2

result:

ok ok

Test #13:

score: 0

Accepted

time: 0ms

memory: 3676kb

input:

output:

YES
1 2 3
1 2 3

result:

ok ok

Test #14:

score: 0

Accepted

time: 0ms

memory: 3732kb

input:

output:

YES
1 2 3 4
3 2 4 1

result:

ok ok

Test #15:

score: 0

Accepted

time: 0ms

memory: 3656kb

input:

output:

YES
1 2 3 4
1 4 3 2

result:

ok ok

Test #16:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

output:

YES
1 4 3 2
2 3 1 4

result:

ok ok

Test #17:

score: 0

Accepted

time: 0ms

memory: 3728kb

input:

output:

YES
1 2 3 4
3 4 1 2

result:

ok ok

Test #18:

score: 0

Accepted

time: 0ms

memory: 3724kb

input:

output:

YES
1 2 3 4
4 3 1 2

result:

ok ok

Test #19:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

output:

YES
1 2 5 4 3
3 1 5 2 4

result:

ok ok

Test #20:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

output:

YES
1 2 3 4 5
3 2 5 1 4

result:

ok ok

Test #21:

score: 0

Accepted

time: 1ms

memory: 3596kb

input:

output:

YES
1 5 2 3 4
3 4 1 5 2

result:

ok ok

Test #22:

score: 0

Accepted

time: 0ms

memory: 3608kb

input:

output:

YES
1 4 2 5 3
3 4 2 5 1

result:

ok ok

Test #23:

score: 0

Accepted

time: 1ms

memory: 3676kb

input:

output:

YES
1 5 3 4 2
3 4 2 1 5

result:

ok ok

Test #24:

score: 0

Accepted

time: 3ms

memory: 3672kb

input:

6
0 0 1 0 0 1
0 0 0 1 1 1
1 0 0 1 1 0
0 1 1 0 1 1
0 1 1 1 0 1
1 1 0 1 1 0

output:

YES
1 5 4 2 3 6
4 3 6 1 2 5

result:

ok ok

Test #25:

score: 0

Accepted

time: 1ms

memory: 3612kb

input:

6
0 0 1 0 1 0
0 0 0 1 1 1
1 0 0 0 1 0
0 1 0 0 0 0
1 1 1 0 0 1
0 1 0 0 1 0

output:

YES
1 3 2 6 5 4
4 1 5 2 6 3

result:

ok ok

Test #26:

score: 0

Accepted

time: 3ms

memory: 3728kb

input:

6
0 0 1 0 1 1
0 0 1 1 0 0
1 1 0 1 0 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 0 1 0 0

output:

YES
1 5 6 2 3 4
3 2 4 1 6 5

result:

ok ok

Test #27:

score: 0

Accepted

time: 1ms

memory: 3676kb

input:

6
0 1 0 1 0 0
1 0 0 0 0 0
0 0 0 0 0 1
1 0 0 0 1 1
0 0 0 1 0 0
0 0 1 1 0 0

output:

YES
1 2 6 5 3 4
4 6 2 5 3 1

result:

ok ok

Test #28:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

6
0 0 0 0 0 1
0 0 1 0 1 1
0 1 0 0 1 1
0 0 0 0 1 1
0 1 1 1 0 0
1 1 1 1 0 0

output:

YES
1 2 3 4 6 5
5 2 3 1 4 6

result:

ok ok

Test #29:

score: 0

Accepted

time: 197ms

memory: 3688kb

input:

7
0 1 0 1 1 0 1
1 0 1 0 1 1 1
0 1 0 0 0 0 0
1 0 0 0 0 0 0
1 1 0 0 0 0 1
0 1 0 0 0 0 1
1 1 0 0 1 1 0

output:

YES
1 7 6 2 3 4 5
3 6 1 7 4 2 5

result:

ok ok

Test #30:

score: 0

Accepted

time: 49ms

memory: 3684kb

input:

7
0 0 1 0 0 1 0
0 0 1 0 1 1 0
1 1 0 0 0 1 1
0 0 0 0 0 1 0
0 1 0 0 0 1 0
1 1 1 1 1 0 1
0 0 1 0 0 1 0

output:

YES
1 3 4 6 5 7 2
5 2 6 1 3 7 4

result:

ok ok

Test #31:

score: -100

Time Limit Exceeded

input:

7
0 0 1 0 0 0 1
0 0 0 1 0 1 0
1 0 0 0 0 0 1
0 1 0 0 0 0 1
0 0 0 0 0 1 1
0 1 0 0 1 0 0
1 0 1 1 1 0 0