QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#669239 | #9246. Dominating Point | mzyx | ML | 2ms | 12232kb | C++20 | 1.4kb | 2024-10-23 17:51:17 | 2024-10-23 17:51:17 |
Judging History
answer
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int N=5001;
bitset<N>baser[N];
bitset<N>basec[N];
int a[N][N];
int b[N][N];
int c[N][N];
int n;
vector<int>ans;
int main()
{
scanf("%d",&n);
int st = clock();
for(int i=1;i<=n;i++)
{
getchar();
for(int j=1;j<=n;j++)
{
char ch;
scanf("%c",&ch);
a[i][j]=(int)(ch-'0');
a[i][j]==1?baser[i][j]=1:baser[i][j]=0;
a[i][j]==1?basec[j][i]=1:basec[j][i]=0;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
bitset<N>T=baser[i]&basec[j];
if(T.any())b[i][j]=1;
else b[i][j]=0;
//printf("%d",b[i][j]);
int ed = clock();
if (ed - st > 950) {
break;
}
}
//printf("\n");
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]==0&&b[i][j]==0)c[i][j]=0;
else c[i][j]=1;
}
}
for(int i=1;i<=n;i++)
{
int flag=1;
for(int j=1;j<=n;j++)
{
if(j==i)continue;
else
{
if(c[i][j]==0)flag=0;
}
}
if(flag)ans.push_back(i);
}
if(ans.size()<3)printf("NOT FOUND\n");
else
{
for(int i=0;i<=2;i++)
{
printf("%d ",ans[i]);
}
printf("\n");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 12120kb
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: 12104kb
input:
3 011 001 000
output:
NOT FOUND
result:
ok OK, Answer correct.
Test #3:
score: 0
Accepted
time: 2ms
memory: 12232kb
input:
3 010 001 100
output:
1 2 3
result:
ok OK, Answer correct.
Test #4:
score: -100
Memory Limit Exceeded
input:
4994 0100001010011001010101110010101000111101111100100001110010000111100000000100110100101000001010100000010010010110110110111010010010100110100000110110111001010111010111010111011001000101001000010001010111110000000100001100000111100011001010010111011100111010101110011000010111101011111110001111110...
output:
NOT FOUND