QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387071#3019. Probe DroidsInfinityNS#TL 0ms10784kbC++171.2kb2024-04-12 01:24:052024-04-12 01:24:06

Judging History

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

  • [2024-04-12 01:24:06]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:10784kb
  • [2024-04-12 01:24:05]
  • 提交

answer

#include<bits/stdc++.h>

#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define ll long long
#define pb push_back
using namespace std;

const int N=1e6+5;
vector<ll> x(N);
int n,m;
ll t;
pair<int,int> ans;
void solve(int i,int j){
    x[i]=x[i-1]+j-1;
    //printf("%i %i: %lld %i %i %lld\n",i,j,x[i],n,m,t);
    ll k=n/i;
    ll sm=(ll)n*m;
    sm-=x[i]*k;
    sm-=k*(k-1)/2*j*i;
    ll ost=n%i;
    sm-=ost*(m-j*k);
    sm-=x[ost];
    //printf("%lld!\n",sm);
    if(sm<t){
        solve(i+1,j);
        return;
    }
    int imam=min((n+1)/i,(m+1)/j);
    ll over=sm-t;
    if(over<=imam-1){
        int ind=imam-over;
        ans={i*ind,j*ind};
        return;
    }
    solve(i,j+1);
}
int main(){
    int q;
    scanf("%i %i %i",&n,&m,&q);
    n--;m--;
    for(int i=0;i<q;i++){
        scanf("%i",&t);
        if(t<=m){
            printf("%i %i\n",1,1+t);
            continue;
        }
        t-=m;
        ll kraj=n*(ll)(m+1)-t;
        if(kraj<n){
            printf("%i %i\n",n-kraj+1,1);
            continue;
        }
        solve(1,1);
        printf("%i %i\n",ans.f+1,ans.s+1);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5 3
1
14
8

output:

1 2
3 1
3 5

result:

ok 6 numbers

Test #2:

score: -100
Time Limit Exceeded

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:


result: