QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#470031#8008. Fortune Wheelbai_hongWA 521ms83924kbC++141.2kb2024-07-10 09:47:232024-07-10 09:47:23

Judging History

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

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

answer

#include<bits/stdc++.h>
const int inf=1e6+5;
const int QWQ=1e5+5;
using namespace std;
inline int read(){
	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;
}
struct node{ int to,next; } E[QWQ*500];
int dep[QWQ],head[QWQ],n,X,K,cnt;
inline void append(int x,int y){
	E[++cnt].to=y;
	E[cnt].next=head[x];
	head[x]=cnt;
}
void bfs(int s){
	for (int i=0;i<n;i++) dep[i]=inf;
	queue<int> q; q.push(s),dep[s]=0;
	while (!q.empty()){
		int u=q.front(); q.pop();
		for (int i=head[u],v;i;i=E[i].next)
			if (dep[v=E[i].to]==inf)
				dep[v]=dep[u]+1,q.push(v);
	}
}
signed main(){
	n=read(),X=read(),K=read();
	for (int i=1;i<=K;i++){
		int k=read();
		for (int u=0;u<n;u++)
			append((u+k)%n,u);
	} 
	bfs(0);
//	for (int i=0;i<n;i++)
//		printf("%d ",dep[i]); puts("");
	int pres=0,A=dep[X],B=1;
	sort(dep,dep+n);
	for (int i=0;i<n;i++)
		if (dep[i]==inf) break;
		else{
			pres+=dep[i];
			if ((long long)(i+1)*A>(long long)(n+pres)*B) A=n+pres,B=i+1;
		}
	int t=__gcd(A,B);
	printf("%d %d\n",A/t,B/t);
	return 0;
} 

详细

Test #1:

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

input:

6 3 2
2 4

output:

8 3

result:

ok 2 number(s): "8 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

5 4 1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

score: 0
Accepted
time: 521ms
memory: 83924kb

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: 2ms
memory: 6592kb

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: 4148kb

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: 5836kb

input:

100 93 4
63 58 3 89

output:

19 4

result:

ok 2 number(s): "19 4"

Test #7:

score: 0
Accepted
time: 5ms
memory: 6400kb

input:

75057 45721 3
10861 27551 14278

output:

32797 933

result:

ok 2 number(s): "32797 933"

Test #8:

score: -100
Wrong Answer
time: 7ms
memory: 6524kb

input:

97777 94043 1
83579

output:

-2147418639 65536

result:

wrong answer 1st numbers differ - expected: '97619', found: '-2147418639'