QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90452 | #896. Horses | Crysfly | WA | 103ms | 9796kb | C++14 | 2.5kb | 2023-03-23 10:03:08 | 2023-03-23 10:03:09 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define mod 998244353
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 300005
#define inf 0x3f3f3f3f
int n,m,a[maxn];
vi p[205];
int e[205][205],fa[205],g[205];
int gf(int x){
while(x^fa[x])x=fa[x]=fa[fa[x]];
return x;
}
vi mg(vi&a,vi&b){
vi c;
int n=a.size(),m=b.size(),i=0,j=0;
while(i<n&&j<m){
if(a[i]<b[j])c.pb(0),++i;
else c.pb(1),++j;
}
while(i<n)c.pb(0),++i;
while(j<m)c.pb(1),++j;
return c;
}
int nxt[maxn];
int period(vi s){
int n=s.size(); nxt[1]=0;
int j=0;
For(i,1,n-1){
while(j&&s[j]!=s[i])j=nxt[j];
if(s[j]==s[i])++j; nxt[i+1]=j;
}
int d=n-nxt[n];
if(n%d==0)return d;
else return n;
}
int st[maxn],top;
int deg[205],now[205],id[205],idx,cnt[205];
vi solve(int rt){
if(p[rt].empty()){
For(i,1,n)if(p[i].size() && e[rt][i])return {};
return {rt};
}
For(i,1,n)deg[i]=id[i]=cnt[i]=0,now[i]=1;
vi o;
For(i,1,n)if(gf(i)==rt)o.pb(i),id[i]=++idx;
For(i,1,m)
if(id[a[i]] && cnt[a[i]]<p[a[i]].size()/g[rt]){
++cnt[a[i]];
st[++top]=a[i];
}
for(auto u:o){
while(now[u]<=top && st[now[u]]!=u)
deg[u]+=e[st[now[u]]][u],++now[u];
}
vi res;
For(_,1,top){
for(auto u:o){
if(now[u]<=top && !deg[u]){
res.pb(u);
for(auto v:o) deg[v]-=e[u][v];
++now[u];
while(now[u]<=top && st[now[u]]!=u)
deg[u]+=e[st[now[u]]][u],++now[u];
break;
}
}
}
return res;
}
signed main()
{
n=read();
For(i,1,n)fa[i]=i;
For(i,1,n)For(j,i+1,n)e[i][j]=e[j][i]=(!(read()));
m=read();
For(i,1,m)p[a[i]=read()].pb(i);
For(i,1,n)
For(j,i+1,n)
if(e[i][j] && p[i].size() && p[j].size()) fa[gf(i)]=gf(j);
For(i,1,n) g[gf(i)]=__gcd(g[gf(i)],(int)p[i].size());
For(i,1,n)
For(j,i+1,n)
if(e[i][j] && p[i].size() && p[j].size()){
vi tmp=mg(p[i],p[j]);
g[gf(i)]=__gcd(g[gf(i)],period(tmp));
}
vector<vi>out;
For(i,1,n)
if(gf(i)==i){
vi o=solve(i);
if(o.size())out.pb(o);
}
sort(out.begin(),out.end());
for(auto t:out){
long long sum=0,pw=1;
for(int x:t)(sum+=x*pw)%=mod,(pw*=n+1)%=mod;
cout<<sum<<"\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3392kb
input:
3 1 1 0 5 2 1 3 2 3
output:
1 14
result:
ok 2 number(s): "1 14"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3460kb
input:
3 0 0 1 6 3 1 3 2 1 2
output:
39
result:
ok 1 number(s): "39"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
4 1 1 1 1 1 1 10 1 2 3 4 4 3 2 1 2 3
output:
1 2 3 4
result:
ok 4 number(s): "1 2 3 4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3340kb
input:
3 1 1 0 5 2 3 2 3 2
output:
1 750
result:
ok 2 number(s): "1 750"
Test #5:
score: -100
Wrong Answer
time: 103ms
memory: 9796kb
input:
200 1 0 1 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 ...
output:
109424727
result:
wrong answer 1st numbers differ - expected: '50576481', found: '109424727'