QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#759 | #498500 | #8008. Fortune Wheel | xinhaowen | xinhaowen | Success! | 2024-07-30 15:38:25 | 2024-07-30 15:38:26 |
Details
Extra Test:
Wrong Answer
time: 0ms
memory: 9452kb
input:
100000 114 1 100000
output:
50001 1
result:
wrong answer 1st numbers differ - expected: '100000', found: '50001'
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#498500 | #8008. Fortune Wheel | xinhaowen | WA | 425ms | 208480kb | C++14 | 1.5kb | 2024-07-30 15:38:06 | 2024-07-30 15:42:11 |
answer
#include<queue>
#include<cstdio>
#include<vector>
#include<algorithm>
//#define getchar getchar_unlocked
//#define putchar putchar_unlocked
template<typename T>void read(T &x){
x=0;bool f=0;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);
if(f)x=-x;
}
void write(char x){putchar(x);}
template<typename T>void write(T x){
if(x<0)putchar('-'),x=-x;
char stk[24];int cnt=0;
do stk[++cnt]=x%10+48,x/=10;while(x);
for(;cnt;)putchar(stk[cnt--]);
}
template<typename T,typename ...Args>void read(T &x,Args &...args){read(x);read(args...);}
template<typename T,typename ...Args>void write(T x,Args ...args){write(x);write(args...);}
template<typename T>T min(T x,T y){return x<y?x:y;}
template<typename T>T max(T x,T y){return x>y?x:y;}
const int maxn=1e5+4;int n,st,k,dis[maxn];std::vector<int>E[maxn];std::queue<int>que;long long A,B;
signed main(){
read(n,st,k);int lim=(n+3)/2;
for(int i=1,x;i<=k;++i){
read(x);
for(int j=0;j<n;++j)E[(j+x)%n].emplace_back(j);
}
for(int i=1;i<n;++i)dis[i]=lim;
que.emplace(0);
for(;que.size();){
int x=que.front();que.pop();
for(int v:E[x])if(dis[v]==lim)dis[v]=dis[x]+1,que.emplace(v);
}
A=dis[st];B=1;std::sort(dis,dis+n);long long sum=0;
for(int i=0;i<n;++i)if(dis[i]!=lim){
// write(i,' ',dis[i],'\n');
sum+=dis[i];
if(B*(n+sum)<A*(i+1))A=n+sum,B=i+1;
}
write(A/std::__gcd(A,B),' ',B/std::__gcd(A,B));
return 0;
}