QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1239 | #772331 | #9246. Dominating Point | xwh_Marvelous | caijianhong | Failed. | 2024-11-22 18:50:44 | 2024-11-22 18:50:45 |
Details
Extra Test:
Accepted
time: 41ms
memory: 6736kb
input:
5000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
NOT FOUND
result:
ok OK, Answer correct.
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#772331 | #9246. Dominating Point | caijianhong | AC ✓ | 123ms | 7012kb | C++23 | 1.2kb | 2024-11-22 18:48:28 | 2024-11-22 18:48:28 |
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;
}