QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#471244#8008. Fortune WheelLZL1251212203WA 669ms168480kbC++141.7kb2024-07-10 19:57:092024-07-10 19:57:10

Judging History

你现在查看的是最新测评结果

  • [2024-07-30 15:38:33]
  • hack成功,自动添加数据
  • (/hack/759)
  • [2024-07-10 19:57:10]
  • 评测
  • 测评结果:WA
  • 用时:669ms
  • 内存:168480kb
  • [2024-07-10 19:57:09]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e7+10;
int n,bg,m;
int skl[N];
struct edge{
	int nxt,to;
}e[N];
int head[N],tot;
void add(int u,int v){
	e[++tot].nxt=head[u];
	e[tot].to=v;
	head[u]=tot;
}
int d[N];
double res;
int up,dw,all;
bool vis[N];
struct num{
	int id,val;
}dis[N],sum[N];
bool cmp(num x,num y){
	return x.val<y.val;
}
void bfs(int x) {
	queue<int> q;
	q.push(x);
	d[0]=0;
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].nxt) {
			int to=e[i].to;
			if(!vis[to]) {
				vis[to]=1;
				d[to]=d[x]+1;
				q.push(to);
			}
		}
	}
}
int gcd(int x,int y){
	if(!y) return x;
	return gcd(y,x%y);
}
int main(){
	cin>>n>>bg>>m;
	memset(d,0x3f,sizeof(d));
	for(int i=1;i<=m;i++) cin>>skl[i];
	for(int i=1;i<n;i++) {
//		add(i,(i+skl[i])%n);
		for(int j=1;j<=m;j++) add((i+skl[j])%n,i);
	}
	bfs(0);
//	d[n]=-1;
	for(int i=1;i<=n;i++) {
		dis[i].id=i-1,dis[i].val=d[i-1];
	}
	sort(dis+1,dis+n+1,cmp);
	for(int i=1;dis[i].val!=1061109567&&i<=n;i++) {
//		cout<<i<<" "<<dis[i].val<<" "<<dis[i].id<<endl;
		sum[i].val=sum[i-1].val+dis[i].val,sum[i].id=dis[i].id;
		all++;
	}
	res=2e9+10;
//	for(int i=1;i<=n;i++) cout<<d[i]<<" ";
//	cout<<all<<endl;
	for(int i=1;i<=all;i++) {
//		cout<<sum[i].id<<" "<<sum[i].val<<endl;
		if(sum[i].id==bg) {
			if((double)sum[i].val/(i-1)<res) {
				res=(double)sum[i].val/(i-1);
				up=sum[i].val;
				dw=i-1;
			}
			continue;
		}
		if((double)(n+sum[i].val)/i < res) {
			res=(double)(n+sum[i].val)/i;
			up=n+sum[i].val;
			dw=i;
		}
	}
	int g=gcd(up,dw);
	cout<<up/g<<" "<<dw/g;
	return 0;
}
/*
6 3 2
2 4

5 4 1
1
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 91564kb

input:

6 3 2
2 4

output:

8 3

result:

ok 2 number(s): "8 3"

Test #2:

score: 0
Accepted
time: 4ms
memory: 89748kb

input:

5 4 1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

score: -100
Wrong Answer
time: 669ms
memory: 168480kb

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:

9977 3896

result:

wrong answer 1st numbers differ - expected: '3', found: '9977'