QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387103#3019. Probe DroidsInfinityNS#WA 0ms18604kbC++171.8kb2024-04-12 02:20:452024-04-12 02:20:46

Judging History

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

  • [2024-04-12 02:20:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:18604kb
  • [2024-04-12 02:20:45]
  • 提交

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);
vector<ll> uzeo(N);
int n,m;
ll t;
pair<int,int> ans;
void solve(int i,int j){
    x[i]=x[i-1]+j-1;
    uzeo[i]=j-1;
    //printf("%i %i: %lld %i %i %lld\n",i,j,x[i],n,m,t);
    ll posle=m/j;
    ll j2=posle*j;
    ll ostalo=m-j2;
    int b=lower_bound(x.begin(),x.begin()+i,ostalo+1)-x.begin()-1;
    ll redova=min((ll)n,posle*i+b);
    //printf("%lld %lld  %lld %i\n",redova,posle,ostalo,b);
    ll k=redova/i;
    ll sm=(ll)redova*m;
    sm-=x[i]*k;
    sm-=k*(k-1)/2*j*i;
    ll ost=redova%i;
    //printf("%lld: %lld %lld\n",sm,ost*(m-j*k),x[ost]);
    sm-=ost*(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);
}
pair<int,int> solve(ll tt){
    t=tt;
    if(t<=m){
        return {0,t};
    }
    t-=m;
    ll kraj=n*(ll)(m+1)-t;
    if(kraj<n){
        return {n-kraj,0};
    }
    solve(1,1);
    return ans;
}
void stres(){
    for(n=0;n<=10;n++){
        for(m=0;m<=10;m++){
            printf("%i %i:\n",n,m);
            for(ll t=1;t<(n+1)*(m+1);t++){
                pair<int,int> a=solve(t);
                printf("%i %i\n",a.f+1,a.s+1);
            }
        }
    }
}
int main(){
    //stres();
    int q;
    scanf("%i %i %i",&n,&m,&q);
    n--;m--;
    for(int i=0;i<q;i++){
        ll tt;
        scanf("%lld",&tt);
        pair<int,int> a=solve(tt);
        printf("%i %i\n",a.f+1,a.s+1);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 18604kb

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:

500005 500005
500011 500011
499955 499955
499973 499973
499966 499966
499991 499991
499972 499972
499986 499986
500048 500048
500022 500022
500043 500043
500024 500024
500000 500000
499978 499978
500042 500042
500027 500027
500003 500003
499999 499999
499970 499970
499969 499969
500034 500034
500030...

result:

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