QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1054#671062#9246. Dominating PointEvanEvanFailed.2024-10-24 10:49:312024-10-24 10:49:31

详细

Extra Test:

Accepted
time: 674ms
memory: 6836kb

input:

5000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

 NOT FOUND

result:

ok OK, Answer correct.

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#671062#9246. Dominating PointEvanAC ✓677ms7144kbC++17973b2024-10-24 10:32:492024-11-22 18:46:56

answer

#include<bits/stdc++.h>
using namespace std;
#define N 5010
bitset<N> s[N],tmp;
int n,cnt[N];
void solve()
{
    scanf("%d",&n);
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        getchar();
        for(j=1;j<=n;j++)
        {
            k=getchar();
            k=k-'0';
            s[i][j]=k;
            if(i==j){s[i][j]=1;}
        }
        cnt[i]=s[i].count();
    }
    vector<int> ans;
    for(i=1;i<=n&&ans.size()<3;i++)
    {
        if(cnt[i]==n){ans.push_back(i);continue;}
        tmp=s[i];
        int tt=cnt[i];
        for(j=1;j<=n;j++)
        {
            if(s[i][j]){tt+=cnt[j];}
        }
        if(tt<=n){continue;}
        for(j=1;j<=n;j++)
        {
            if(s[i][j]){tmp|=s[j];}
        }
        if(tmp.count()==n){ans.push_back(i);}
    }
    if(ans.size()==3){printf("%d %d %d\n",ans[0],ans[1],ans[2]);}
    else{printf(" NOT FOUND\n");}
}
int main()
{
    int t=1;
    while(t--){solve();}
}