QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#678724#9246. Dominating Pointveg#WA 157ms3892kbC++201.1kb2024-10-26 15:54:012024-10-26 15:54:01

Judging History

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

  • [2024-11-22 18:38:25]
  • hack成功,自动添加数据
  • (/hack/1238)
  • [2024-10-26 15:54:01]
  • 评测
  • 测评结果:WA
  • 用时:157ms
  • 内存:3892kb
  • [2024-10-26 15:54:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n, d[5005];
const int N = 10;
char s[5005];
bitset<N> a[5000];
bitset<N> pre[5000];
vector<pair<int, int> > v;
vector<int> ans;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%s", s);
		for (int j = 0; j < n; ++j) {
			a[i][j] = s[j] - '0';
			if (s[j] == '1') {
				++d[j];
				pre[j][i] = 1;
			}
		}
	}
	for (int i = 0; i < n; ++i)
		v.push_back({d[i], i});
	sort(v.begin(), v.end());
	bitset<N> ret;
	ret.set();
	for (int i = 0; i < 50 && i < v.size(); ++i) {
		if (pre[v[i].second].none()) {}
		else {
			auto tmp = pre[pre[v[i].second]._Find_first()] | pre[v[i].second];
			tmp[v[i].second] = 1;
			ret &= tmp;
		}
	}
	for (int i = 0; i < n; ++i)
		if (ret[i]) {
			bitset<N> test = a[i];
			test[i] = 1;
			for (int x = 0; x < n; ++x)
				if (a[i][x])
					test |= a[x];
			if (test.count() == n) {
				ans.push_back(i);
				if (ans.size() == 3) break;
			}
		}
	if (ans.size() < 3) puts("NOT FOUND");
	else printf("%d %d %d\n", ans[0] + 1, ans[1] + 1, ans[2] + 1);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6
011010
000101
010111
100001
010100
100010

output:

1 3 4

result:

ok OK, Answer correct.

Test #2:

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

input:

3
011
001
000

output:

NOT FOUND

result:

ok OK, Answer correct.

Test #3:

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

input:

3
010
001
100

output:

1 2 3

result:

ok OK, Answer correct.

Test #4:

score: -100
Wrong Answer
time: 157ms
memory: 3892kb

input:

4994
0100001010011001010101110010101000111101111100100001110010000111100000000100110100101000001010100000010010010110110110111010010010100110100000110110111001010111010111010111011001000101001000010001010111110000000100001100000111100011001010010111011100111010101110011000010111101011111110001111110...

output:

NOT FOUND

result:

wrong output format Expected integer, but "NOT" found