QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#551766 | #3019. Probe Droids | PhantomThreshold# | WA | 1ms | 3740kb | C++20 | 2.1kb | 2024-09-07 18:00:48 | 2024-09-07 18:00:49 |
Judging History
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<=41;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<=41;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: 3740kb
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: 3608kb
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'