QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #498322 | #8008. Fortune Wheel | 123456xwd | WA | 21ms | 4712kb | C++14 | 1.2kb | 2024-07-30 11:52:42 | 2024-07-30 11:52:43 |
Judging History
answer
#include<bits/stdc++.h>
//#define int long long
#define m_p make_pair
#define p_b push_back
using namespace std;
inline int rd(){
int x=0,f=1; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
const int N=1e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,x,K;
int k[N];
int deep[N];
void bfs(){
queue<int> q;
memset(deep,0x3f,sizeof(deep));
deep[0]=0,q.push(0);
int u,v;
while(!q.empty()){
u=q.front();q.pop();
for(int i=1;i<=K;i++){
v=(u+n-k[i])%n;//相当于是逆着走
if(deep[v]>deep[u]+1){
deep[v]=deep[u]+1;
q.push(v);
}
}
}
}
struct frac{
int up,down;
bool friend operator <(const frac &a,const frac &b){
return a.up*b.down<b.up*a.down;
}
void clean(){
int x=__gcd(up,down);
up/=x,down/=x;
}
};
signed main(){
n=rd(),x=rd(),K=rd();
for(int i=1;i<=K;i++) k[i]=rd();
bfs();
frac ans={deep[x],1},tmp;
sort(deep,deep+n);
int sum=0;
for(int i=0;i<n;i++){
if(deep[i]==INF) break;
sum+=deep[i];
tmp={sum+n,i+1};
if(tmp<ans) ans=tmp;
}
ans.clean();
printf("%lld %lld\n",ans.up,ans.down);
return 0;
}//fdsaaaaaaaaa
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4396kb
input:
6 3 2 2 4
output:
8 3
result:
ok 2 number(s): "8 3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4224kb
input:
5 4 1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 21ms
memory: 4712kb
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: 1ms
memory: 4172kb
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: 4392kb
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: 1ms
memory: 4136kb
input:
100 93 4 63 58 3 89
output:
19 4
result:
ok 2 number(s): "19 4"
Test #7:
score: -100
Wrong Answer
time: 3ms
memory: 4432kb
input:
75057 45721 3 10861 27551 14278
output:
5206529 74961
result:
wrong answer 1st numbers differ - expected: '32797', found: '5206529'