QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1238 | #772304 | #9246. Dominating Point | caijianhong | caijianhong | Success! | 2024-11-22 18:37:34 | 2024-11-22 18:37:35 |
Details
Extra Test:
Wrong Answer
time: 0ms
memory: 3888kb
input:
4 0101 0011 1001 0000
output:
NOT FOUND
result:
wrong output format Expected integer, but "NOT" found
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#772304 | #9246. Dominating Point | caijianhong | WA | 125ms | 7016kb | C++23 | 1.2kb | 2024-11-22 18:30:53 | 2024-11-22 18:49:42 |
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
int n, deg[5010], d2[5010];
bitset<5010> g[5010];
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n;
for (int i = 1; i <= n; i++) {
static char buf[5010];
cin >> buf;
for (int j = 1; j <= n; j++) if (buf[j - 1] == '1') g[i][j] = true, ++deg[i];
}
vector<int> vec, per(n);
iota(per.begin(), per.end(), 1);
sort(per.begin(), per.end(), [&](int i, int j) { return deg[i] > deg[j]; });
memcpy(d2, deg, sizeof d2);
sort(d2 + 1, d2 + n + 1);
for (int i = 1, pre = 0; i < n; i++) if ((pre += d2[i]) == i * (i - 1) / 2) return cout << "NOT FOUND" << endl, debug("i = %d\n", i), 0;
for (int i = 0; i < n; i++) {
bool flag = false;
for (int j = 0; j < i && !flag; j++) if ((g[per[i]] & g[per[j]]) == g[per[i]]) flag = true, debug("i = %d, j = %d\n", per[i], per[j]);
if (!flag) vec.push_back(per[i]);
if (vec.size() >= 3) break;
}
if (vec.size() < 3) cout << "NOT FOUND" << endl;
else cout << vec[0] << " " << vec[1] << " " << vec[2] << endl;
return 0;
}