QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#759#498500#8008. Fortune WheelxinhaowenxinhaowenSuccess!2024-07-30 15:38:252024-07-30 15:38:26

详细

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题目提交者结果用时内存语言文件大小提交时间测评时间
#498500#8008. Fortune WheelxinhaowenWA 425ms208480kbC++141.5kb2024-07-30 15:38:062024-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;
}