QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#375763#4682. Pipe StreamInfinityNSTL 1ms3836kbC++141.1kb2024-04-03 15:38:242024-04-03 15:38:25

Judging History

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

  • [2024-04-03 15:38:25]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3836kb
  • [2024-04-03 15:38:24]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back

using namespace std;

int l,s,t;
int solve(int v1, int v2, int knock){
    if(v2-v1<=t)return knock;
    int slt=(knock+1)*s;
    int vl=(v1+v2)/2,vr=v2-t;
    vl=min(vl,vr);
    ll pos=(ll)vr*slt;
    if(pos>l)return -1;
    int ans=-1;
    while(vl<=vr){
        int vm=(vl+vr)>>1;
        ll pos=(ll)vm*slt;
        int r=solve(vm,v2,knock+1);
        bool ok=1;
        if(r!=-1){
            int l=solve(v1,vm,knock+1);
            if(l==-1){
                r=-1;
            }
            else{
                r=max(r,l);
            }
        }
        if(r==-1){
            vl=vm+1;
        }
        else{
            ans=r;
            vr=vm-1;
        }
    }
    return ans;
}


int main(){
    int o;
    scanf("%i",&o);
    while(o--){
        int v1,v2;
        scanf("%i %i %i %i %i",&l,&v1,&v2,&t,&s);
        int x=solve(v1,v2,0);
        if(x==-1){
            printf("impossible\n");
        }
        else{
            printf("%i\n",x);
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3836kb

input:

3
1000 1 30 1 1
60 2 10 2 5
59 2 10 2 5

output:

5
3
impossible

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

input:

100
1 1 2 1 1
1 1 3 1 1
2 1 3 1 1
3 1 4 1 1
4 1 4 1 1
100000 1 1000000 1 1
100000 1 9 1 1
100000 1 9454 1 1
100000 1 9455 1 1
500832 1 40181 1 1
500832 1 40182 1 1
524288 1 41871 1 1
524288 1 41872 1 1
930168 1 70677 1 1
930168 1 70678 1 1
930169 1 70677 1 1
930169 1 70678 1 1
930170 1 70677 1 1
930...

output:


result: