QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558499#3019. Probe DroidsPhantomThresholdWA 760ms3588kbC++172.7kb2024-09-11 16:31:522024-09-11 16:31:52

Judging History

This is the latest submission verdict.

  • [2024-09-11 16:31:52]
  • Judged
  • Verdict: WA
  • Time: 760ms
  • Memory: 3588kb
  • [2024-09-11 16:31:52]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
using ll=__int128;
namespace el
{
	typedef long long ll;
	struct ifo{
		ll f,g,h;
		ifo(ll _f,ll _g,ll _h):f(_f),g(_g),h(_h){}
	};
	ll S1(ll n){
		return n*(n+1)/2;
	}
	ll S2(ll n){
		return n*(n+1)*(2*n+1)/6;
	}
	ifo Get(ll n,ll A,ll B,ll C){
		if (!A){
			ll t=B/C;
			ll f=(n+1)*t;
			ll g=S1(n)*t;
			ll h=(n+1)*t*t;
			return ifo(f,g,h);
		}
		else if (A>=C || B>=C){
			ifo Nx=Get(n,A%C,B%C,C);
			ll p=A/C,q=B/C;
			ll f=(p*S1(n)+q*(n+1)+Nx.f);
			ll g=(p*S2(n)+q*S1(n)+Nx.g);
			ll h=(p*p*S2(n)+2*p*q*S1(n)
			+(n+1)*q*q+2*p*Nx.g+2*q*Nx.f+Nx.h);
			return ifo(f,g,h);
		}
		else{
			ll m=(A*n+B)/C;
			ifo Nx=Get(m-1,C,C-B-1,A);
			ll f=((n*m-Nx.f));
			ll g=((2*m*S1(n)-Nx.h-Nx.f)/2);
			ll h=((2*n*S1(m-1)+n*m-2*Nx.g-Nx.f));
			return ifo(f,g,h);
		}
	}
	ll f(ll n,ll a,ll b,ll c)
	{
		return Get(n,a,b,c).f; 
	}
}
ll gcd(ll x,ll y)
{
	if(y==0)return x;
	return gcd(y,x%y);
}
int main()
{
	long long 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5 3
1
14
8

output:

1 2
3 1
3 5

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 751ms
memory: 3588kb

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:

500004 500004
500010 500010
499954 499954
499972 499972
499965 499965
499990 499990
499971 499971
499985 499985
500047 500047
500021 500021
500042 500042
500023 500023
499999 499999
499977 499977
500041 500041
500026 500026
500002 500002
499998 499998
499969 499969
499968 499968
500033 500033
500029...

result:

ok 200 numbers

Test #3:

score: -100
Wrong Answer
time: 760ms
memory: 3536kb

input:

1000000 1000000 100
791524265480
310246148308
965405638061
748161462511
437425441834
859125430870
318755212730
838283037379
290597520864
840800992509
318819733413
235852029334
308150887842
829080735481
847795824828
806338877319
658498289208
599749991035
951485631667
503061373811
165065406989
4217028...

output:

881949 367730
-1197397 -1929755
545921 37772
272265 137134
-2916335 -3333523
865674 243903
-1636859 -2567582
750870 242857
1 1
564610 179771
1 1
1 1
1 1
929544 317754
703459 214139
996470 385955
660957 451436
983158 787018
726710 70512
160713 159729
1 1
1 1
823356 577575
509029 435006
1 1
856326 455...

result:

wrong answer 3rd numbers differ - expected: '455761', found: '-1197397'