QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#469932#8008. Fortune WheeljiaziqiAC ✓89ms5376kbC++14863b2024-07-10 09:03:252024-07-30 15:40:31

Judging History

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

  • [2024-07-30 15:40:31]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果：AC
  • 用时：89ms
  • 内存：5376kb
查看
  • [2024-07-30 15:38:33]
  • hack成功，自动添加数据
  • (/hack/759)
  • [2024-07-10 09:03:27]
  • 评测
  • 测评结果：100
  • 用时：96ms
  • 内存：5368kb
查看
  • [2024-07-10 09:03:25]
  • 提交

answer

#include<bits/stdc++.h>
#define ShuaiBi main
using namespace std;
typedef long long ll;
const int N=1e5+3;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,X,k,a[503],id[N];
ll dis[N];
bool cmp(int x,int y){return dis[x]<dis[y];}
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
queue<int> q;
void bfs(){
	q.push(0),dis[0]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=1;i<=k;i++){
			int v=(u-a[i]+n)%n;
			if(dis[v]==inf) dis[v]=dis[u]+1,q.push(v);
		}
	}
}
int ShuaiBi(){
	memset(dis,0x3f,sizeof(dis));
	scanf("%d%d%d",&n,&X,&k);
	for(int i=1;i<=k;i++) scanf("%d",a+i);
	for(int i=0;i<n;i++) id[i]=i;
	bfs();
	sort(id,id+n,cmp);
	ll p=dis[X],q=1,sum=0;
	for(int i=0;i<n;i++){
		if(dis[id[i]]==inf) break;
		sum+=dis[id[i]];
		if((sum+n)*q<p*(i+1)) p=sum+n,q=i+1;
	}
	printf("%lld %lld\n",p/gcd(p,q),q/gcd(p,q));
	return 0;
}
Source code, Language: C++14

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4808kb

input:

6 3 2
2 4

output:

8 3

result:

ok 2 number(s): "8 3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4840kb

input:

5 4 1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

score: 0
Accepted
time: 23ms
memory: 5244kb

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

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

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

input:

100 93 4
63 58 3 89

output:

19 4

result:

ok 2 number(s): "19 4"

Test #7:

score: 0
Accepted
time: 6ms
memory: 4944kb

input:

75057 45721 3
10861 27551 14278

output:

32797 933

result:

ok 2 number(s): "32797 933"

Test #8:

score: 0
Accepted
time: 11ms
memory: 4924kb

input:

97777 94043 1
83579

output:

97619 221

result:

ok 2 number(s): "97619 221"

Test #9:

score: 0
Accepted
time: 1ms
memory: 4564kb

input:

13515 10596 5
11890 9097 4596 13464 13309

output:

6022 489

result:

ok 2 number(s): "6022 489"

Test #10:

score: 0
Accepted
time: 6ms
memory: 4912kb

input:

77777 64477 3
45863 40922 74543

output:

298537 8416

result:

ok 2 number(s): "298537 8416"

Test #11:

score: 0
Accepted
time: 1ms
memory: 4632kb

input:

1 0 1
1

output:

0 1

result:

ok 2 number(s): "0 1"

Test #12:

score: 0
Accepted
time: 2ms
memory: 4724kb

input:

11254 5306 33
4933 97 3341 7991 766 11039 6490 8955 10986 642 421 4570 9198 3221 9106 5076 8660 517 8376 4918 10847 10400 9063 8416 4673 7139 3925 7192 8391 7763 4927 10373 3726

output:

3 1

result:

ok 2 number(s): "3 1"

Test #13:

score: 0
Accepted
time: 1ms
memory: 4636kb

input:

33 32 6
20 26 25 18 5 28

output:

101 32

result:

ok 2 number(s): "101 32"

Test #14:

score: 0
Accepted
time: 18ms
memory: 5044kb

input:

100000 56979 500
6945 45095 52485 23545 72920 30450 64925 31700 11155 65550 80965 77885 97915 26950 86940 50045 46645 74740 35235 13470 18315 72135 25260 88775 4405 25525 61335 97040 13240 2905 37460 51605 2330 54995 17100 30790 68205 53195 63340 85495 48535 94865 87720 52930 30650 47115 68380 24455...

output:

13953 2000

result:

ok 2 number(s): "13953 2000"

Test #15:

score: 0
Accepted
time: 48ms
memory: 5376kb

input:

100000 88341 500
35014 85376 26718 27010 22158 56540 54016 52932 81956 92630 79862 844 37070 30304 9780 50642 56332 91384 20562 17764 94836 28314 23928 46364 59128 5820 21488 60066 5262 8964 53054 28310 79006 92364 20872 34916 10934 56274 1020 23138 70610 85702 56844 99122 56842 8772 61584 5346 4819...

output:

40687 10000

result:

ok 2 number(s): "40687 10000"

Test #16:

score: 0
Accepted
time: 89ms
memory: 5112kb

input:

100000 80536 500
91882 33957 97622 44074 36850 17254 63750 32583 12125 43292 58710 2227 31892 64531 13775 20782 72858 85509 37363 57708 26191 2037 8279 5828 38370 88145 76527 73627 28868 68151 31497 78935 1779 63126 37781 57818 46131 81930 43171 25281 1175 90726 12883 73954 7094 46278 62218 33972 54...

output:

2 1

result:

ok 2 number(s): "2 1"

Test #17:

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

input:

100000 14944 4
76800 80400 34400 91600

output:

101433 250

result:

ok 2 number(s): "101433 250"

Test #18:

score: 0
Accepted
time: 14ms
memory: 5096kb

input:

100000 26729 100
31512 64212 8166 14162 80024 52426 94306 14110 22268 53434 38668 16458 16622 2704 28246 72148 28688 59992 53220 13012 39628 8452 52162 21652 93712 79296 5692 41374 22558 91772 92492 93806 81856 54222 32254 11294 74172 47658 67984 41378 83042 3434 21248 82852 51372 62316 26610 26536 ...

output:

24639 5000

result:

ok 2 number(s): "24639 5000"

Test #19:

score: 0
Accepted
time: 6ms
memory: 5024kb

input:

99999 30274 13
51864 40473 61395 72180 91728 53574 49005 42855 71625 92499 441 95985 99123

output:

308066 33333

result:

ok 2 number(s): "308066 33333"

Test #20:

score: 0
Accepted
time: 3ms
memory: 4836kb

input:

72000 53726 7
70632 15840 58896 57312 46440 38376 64368

output:

9633 125

result:

ok 2 number(s): "9633 125"

Test #21:

score: 0
Accepted
time: 1ms
memory: 4552kb

input:

512 179 5
424 8 128 280 256

output:

707 64

result:

ok 2 number(s): "707 64"

Test #22:

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

input:

99855 34584 8
45675 3780 4725 6930 75285 34335 41895 50400

output:

101037 317

result:

ok 2 number(s): "101037 317"

Test #23:

score: 0
Accepted
time: 3ms
memory: 4996kb

input:

88888 49866 3
88888 44444 22222

output:

22223 1

result:

ok 2 number(s): "22223 1"

Test #24:

score: 0
Accepted
time: 1ms
memory: 4580kb

input:

16 11 1
12

output:

11 2

result:

ok 2 number(s): "11 2"

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-11-30 06:36:55 | OpenSource Project