QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558499 | #3019. Probe Droids | PhantomThreshold | WA | 760ms | 3588kb | C++17 | 2.7kb | 2024-09-11 16:31:52 | 2024-09-11 16:31:52 |
Judging History
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'