QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#551776#3019. Probe DroidsPhantomThreshold#WA 1ms3748kbC++202.1kb2024-09-07 18:02:002024-09-07 18:02:04

Judging History

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

  • [2024-09-07 18:02:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3748kb
  • [2024-09-07 18:02:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=__int128;
namespace el
{
	ll f(ll n,ll a,ll b,ll c)
	{
		if(b>=c)return f(n,a,b%c,c)+(b/c)*(n+1);
		if(a>=c)return f(n,a%c,b,c)+(a/c)*(n*(n+1)/2);
		ll m=(n*a+b)/c;
		if(m==0)return 0;
		return n*m-f(m-1,c,c-b-1,a);
	}
}
ll gcd(ll x,ll y)
{
	if(y==0)return x;
	return gcd(y,x%y);
}
int main()
{
	int n,m,T;
	cin>>n>>m>>T;

	auto solve=[&](ll x,ll y)
	{
		ll g=gcd(x,y);
		x/=g;y/=g;
		if(y*(m-1)<=(n-1)*x)
		{
			ll tmp=el::f(m-1,y,0,x)+m-1;
			ll cc=min((m-1)/x,(n-1)/y);
			return tmp-cc;
		}
		else
		{
			ll tmp=el::f(n-1,x,0,y)+n;
			return n*m-tmp;
		}
	};
//	cerr<<solve(3,2)<<endl;
	while(T--)
	{
		long long k;
		cin>>k;
		if(k<=m-1)
		{
			cout<<1<<' '<<(long long)(k+1)<<"\n";
		}
		else if(k>=n*m-1-(n-1)+1)
		{
			cout<<(long long)(k-(n*m-1-(n-1))+1)<<' '<<1<<"\n";
		}
		else if(k<=n*m/2)
		{
			ll lp=0,rp=n-1;
			ll q=m-1;
			for(int tt=1;tt<=61;tt++)
			{
//				cerr<<lp<<' '<<rp<<' '<<q<<endl;
				ll mp=(lp+rp);
				ll mq=q*2;
//				cerr<<mp<<' '<<mq<<' '<<solve(mp,mq)<<endl;
				if(solve(mq,mp)>=k)rp=mp,lp*=2;
				else lp=mp,rp*=2;
				q=mq;
			}
			ll bestx=0,besty=0;
			for(int i=1;i<=m-1;i++)
			{
				ll y=(i*lp+q-1)/q,x=i;
				if(bestx==0 or x*besty-y*bestx>0)bestx=x,besty=y;
			}
			ll g=gcd(bestx,besty);
			bestx/=g;besty/=g;
			ll cntr=solve(bestx,besty);
			k-=cntr;
			cout<<(long long)(1+k*besty)<<' '<<(long long)(1+k*bestx)<<"\n";
		}
		else
		{
			ll p=n-1;
			ll lq=0,rq=m-1;
			for(int tt=1;tt<=61;tt++)
			{
				ll mp=p*2;
				ll mq=(lq+rq);
				if(solve(mq,mp)>=k)lq=mq,rq*=2;
				else rq=mq,lq*=2;
				p=mp;
			}
//			cerr<<p<<' '<<rq<<endl;
//			cerr<<1.0*p/rq<<endl;
			ll bestx=0,besty=0;
			for(int i=1;i<=n-1;i++)
			{
				ll y=i,x=rq*i/p;
				if(bestx==0 or x*besty-y*bestx>0)bestx=x,besty=y;
			}
			ll g=gcd(bestx,besty);
			bestx/=g;besty/=g;
			ll cntr=solve(bestx,besty);
//			cerr<<bestx<<' '<<besty<<' '<<cntr<<endl;
			k-=cntr;
			cout<<(long long)(1+k*besty)<<' '<<(long long)(1+k*bestx)<<"\n";
		}
	}

	return 0;
}

详细

Test #1:

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

input:

3 5 3
1
14
8

output:

1 2
3 1
3 5

result:

ok 6 numbers

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3748kb

input:

1000000 1000000 100
500000000003
500000000009
499999999953
499999999971
499999999964
499999999989
499999999970
499999999984
500000000046
500000000020
500000000041
500000000022
499999999998
499999999976
500000000040
500000000025
500000000001
499999999997
499999999968
499999999967
500000000032
5000000...

output:

500728379972 1
500728379978 1
500728379922 1
500728379940 1
500728379933 1
500728379958 1
500728379939 1
500728379953 1
500728380015 1
500728379989 1
500728380010 1
500728379991 1
500728379967 1
500728379945 1
500728380009 1
500728379994 1
500728379970 1
500728379966 1
500728379937 1
500728379936 1
...

result:

wrong answer 1st numbers differ - expected: '500004', found: '500728379972'