QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#527082#8008. Fortune WheelChrysanthBlossomWA 76ms199772kbC++141.7kb2024-08-22 09:55:272024-08-22 09:55:28

Judging History

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

  • [2024-08-22 09:55:28]
  • 评测
  • 测评结果:WA
  • 用时:76ms
  • 内存:199772kb
  • [2024-08-22 09:55:27]
  • 提交

answer

#include<bits/stdc++.h> 
#define ri register int
#define ll long long
#define mkp make_pair
#define ld long double 
using namespace std;
const int maxn=1e5+7;
int n,x,K;
int k[maxn];
int f[501][maxn];
const int inf=1e9;
int a[maxn];
struct Frac{
	ll fz,fm;
	Frac () {}
	Frac (ll a,ll b=1):fz(a),fm(b){
		if(fm<0)fm=-fm,fz=-fz;
		ll g=__gcd(abs(a),abs(b));
		fz/=g;fm/=g;
	}
	friend Frac operator + (Frac a,Frac b){return Frac(a.fz*b.fm+a.fm*b.fz,a.fm*b.fm);}
	friend Frac operator - (Frac a,Frac b){return Frac(a.fz*b.fm-a.fm*b.fz,a.fm*b.fm);}
	friend Frac operator * (Frac a,Frac b){return Frac(a.fz*b.fz,a.fm*b.fm);}
	friend Frac operator / (Frac a,Frac b){return Frac(a.fz*b.fm,a.fm*b.fz);}
	friend bool operator < (Frac a,Frac b){return (a-b).fz<0;}
	friend bool operator > (Frac a,Frac b){return (a-b).fz>0;}
	friend bool operator == (Frac a,Frac b){return (a-b).fz==0;}
	friend bool operator <= (Frac a,Frac b){return !(a>b);}
	friend bool operator >= (Frac a,Frac b){return !(a<b);}
	void print_fs(){cout<<fz<<' '<<fm;}
	void print(){cout<<(ld)(fz)/(ld)(fm);}
};
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>x>>K;
	for(ri i=1;i<=K;i++)cin>>k[i];
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(ri i=1;i<=K;i++){
		for(ri j=0;j<n;j++)f[i][j]=f[i-1][j];
		for(ri j=0;j<n;j++)f[i][j]=min(f[i][j],f[i-1][(j+k[i])%n]+1);
		for(ri j=0;j<n;j++)f[i][j]=min(f[i][j],f[i-1][(j-k[i]+n)%n]+1);
	}
	for(ri i=0;i<n;i++)a[i]=f[K][i];
	sort(a,a+n);
	Frac ans=Frac(f[K][x]);
	int sum=0;
//	for(ri i=0;i<n;i++)cout<<a[i]<<' ';cout<<endl;
	for(ri i=0;i<n;i++){
		if(a[i]>n*K)continue;
		sum+=a[i];
		ans=min(ans,(Frac(sum)/Frac(i+1))+(Frac(n)/Frac(i+1)));
	}
	ans.print_fs();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 199596kb

input:

6 3 2
2 4

output:

8 3

result:

ok 2 number(s): "8 3"

Test #2:

score: 0
Accepted
time: 7ms
memory: 199356kb

input:

5 4 1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

score: 0
Accepted
time: 76ms
memory: 199772kb

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: -100
Wrong Answer
time: 11ms
memory: 199464kb

input:

10000 23 7
9594 8998 9330 6851 1662 6719 583

output:

6 1

result:

wrong answer 1st numbers differ - expected: '42726', found: '6'