QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#524324 | #8008. Fortune Wheel | Mitsukasa_Ayase# | TL | 118ms | 5944kb | C++14 | 1.8kb | 2024-08-19 15:47:07 | 2024-08-19 15:47:08 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
struct fac{
ll p,q;
};
fac norm(ll a,ll b){
ll gc=__gcd(a,b);
return (fac){a/gc,b/gc};
}
fac add(fac a,fac b){
ll c=a.p*b.q+b.p*a.q;
ll d=a.q*b.q;
return norm(c,d);
}
bool cmp(fac a,fac b){
return a.p*b.q<=a.q*b.p;
}
int st[N],vis[N],tot;
fac dis[N],sum;
queue<int> q;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,x,k;
cin>>n>>x>>k;
for(int i=1;i<=k;++i)
cin>>st[i];
for(int i=0;i<n;++i) dis[i]=(fac){1000000000000,1};
dis[0]=(fac){0,1};
q.push(0);
sum=(fac){0,1};
for(int t=-1;t<n;++t){
if(t>=0&&vis[t]==0){
q.push(t);
dis[t]=(fac){1000000000000ll,1};
}
while(!q.empty()){
int u=q.front(); q.pop();
// cerr<<u<<endl;
if(vis[u]) continue;
// cerr<<"act "<<u<<endl;
if(u!=0){
fac a=sum;
a.q*=tot;
fac tmp=add(a,norm(n,tot));
// cerr<<a.p<<" "<<a.q<<endl;
// cerr<<tot<<endl;
// cerr<<u<<" "<<tmp.p<<" "<<tmp.q<<" "<<dis[u].p<<" "<<dis[u].q<<endl;
if(cmp(tmp,dis[u]))
dis[u]=tmp;
}
sum=add(sum,dis[u]);
vis[u]=1;
++tot;
for(int i=1;i<=k;++i){
int p=(u-st[i]+n)%n;
if(cmp(dis[p],add(dis[u],(fac){1,1}))) continue;
q.push(p);
dis[p]=add(dis[u],(fac){1,1});
}
// cerr<<"ed "<<u<<endl;
// cerr<<dis[u].p<<" "<<dis[u].q<<endl;
}
}
fac ans=norm(dis[x].p,dis[x].q);
cout<<ans.p<<" "<<ans.q<<'\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
input:
6 3 2 2 4
output:
8 3
result:
ok 2 number(s): "8 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5600kb
input:
5 4 1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 118ms
memory: 5944kb
input:
99999 65238 100 64714 45675 36156 13116 93455 22785 10977 60219 14981 25839 83709 80404 41400 12469 31530 65521 35436 20326 96792 50699 27522 98233 26187 12509 90992 72693 83919 74145 80892 68422 38333 33497 89154 88403 77492 4570 3908 59194 3482 89871 96330 45114 5555 73987 95832 476 949 74649 2084...
output:
3 1
result:
ok 2 number(s): "3 1"
Test #4:
score: 0
Accepted
time: 4ms
memory: 3832kb
input:
10000 23 7 9594 8998 9330 6851 1662 6719 583
output:
42726 4805
result:
ok 2 number(s): "42726 4805"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
100 3 100 7 68 28 98 19 32 90 79 92 40 96 30 95 91 71 15 33 18 69 1 61 43 5 75 73 64 58 100 88 20 99 37 17 22 82 67 70 55 47 80 66 12 4 24 26 54 74 57 21 77 86 89 83 29 46 31 2 16 49 48 25 93 52 9 85 84 42 39 8 65 10 45 63 87 78 60 23 14 34 59 81 38 41 76 3 13 27 36 35 51 44 62 53 94 6 50 11 97 72 56
output:
1 1
result:
ok 2 number(s): "1 1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
100 93 4 63 58 3 89
output:
19 4
result:
ok 2 number(s): "19 4"
Test #7:
score: 0
Accepted
time: 15ms
memory: 5088kb
input:
75057 45721 3 10861 27551 14278
output:
32797 933
result:
ok 2 number(s): "32797 933"
Test #8:
score: 0
Accepted
time: 20ms
memory: 5536kb
input:
97777 94043 1 83579
output:
97619 221
result:
ok 2 number(s): "97619 221"
Test #9:
score: 0
Accepted
time: 2ms
memory: 3872kb
input:
13515 10596 5 11890 9097 4596 13464 13309
output:
6022 489
result:
ok 2 number(s): "6022 489"
Test #10:
score: 0
Accepted
time: 22ms
memory: 5084kb
input:
77777 64477 3 45863 40922 74543
output:
298537 8416
result:
ok 2 number(s): "298537 8416"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
1 0 1 1
output:
0 1
result:
ok 2 number(s): "0 1"
Test #12:
score: 0
Accepted
time: 6ms
memory: 3884kb
input:
11254 5306 33 4933 97 3341 7991 766 11039 6490 8955 10986 642 421 4570 9198 3221 9106 5076 8660 517 8376 4918 10847 10400 9063 8416 4673 7139 3925 7192 8391 7763 4927 10373 3726
output:
3 1
result:
ok 2 number(s): "3 1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
33 32 6 20 26 25 18 5 28
output:
101 32
result:
ok 2 number(s): "101 32"
Test #14:
score: -100
Time Limit Exceeded
input:
100000 56979 500 6945 45095 52485 23545 72920 30450 64925 31700 11155 65550 80965 77885 97915 26950 86940 50045 46645 74740 35235 13470 18315 72135 25260 88775 4405 25525 61335 97040 13240 2905 37460 51605 2330 54995 17100 30790 68205 53195 63340 85495 48535 94865 87720 52930 30650 47115 68380 24455...