QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#387103 | #3019. Probe Droids | InfinityNS# | WA | 0ms | 18604kb | C++17 | 1.8kb | 2024-04-12 02:20:45 | 2024-04-12 02:20:46 |
Judging History
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);
}
}
详细
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'