QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#413412#6749. TargetSSHL#TL 3ms5808kbC++141.4kb2024-05-17 15:00:182024-05-17 15:00:18

Judging History

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

  • [2024-05-17 15:00:18]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:5808kb
  • [2024-05-17 15:00:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int mod = 998244353;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    double a,b;
    cin>>a>>b;
    queue<double>q;
    q.push(a);
    set<double>st;
    st.insert(a);
    double ans=0;
    map<pair<double,double>,int>mp;
    while(!q.empty())
    {
        double x=q.front();
        q.pop();
        if(abs(x-b)<=0.0001)
        {
            ans=x;
            break;
        }
        double tmp=x;
        tmp/=2;
        if(st.count(tmp)==0)
        {
            mp[{x,tmp}]=1;
            st.insert(tmp);
            q.push(tmp);
        }
        tmp+=(double)0.5;
        if(st.count(tmp)==0)
        {
            mp[{x,tmp}]=2;
            st.insert(tmp);
            q.push(tmp);
        }
    }
    // cout<<ans<<endl;
    vector<int>v;
    // cout<<mp[{0.5,0.75}]<<endl;
    int x=50;
    // cout<<ans*2<<" "<<ans*2-1<<" "<<ans<<endl;
    while(ans!=a)
    {
        // cout<<ans*2<<" "<<ans*2-1<<" "<<ans<<endl;
        // cout<<mp[{ans*2,ans}]<<" "<<mp[{(2*ans-1),ans}]<<endl;
        if(mp[{ans*2,ans}]==1)
        {
            ans*=2;
            v.push_back(1);
        }
        else if(mp[{(2*ans-1),ans}]==2)
        {
            ans=2*ans-1;
            v.push_back(2);
        }
    }
    reverse(v.begin(),v.end());
    for(auto i:v)
    {
        cout<<i;
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

0.5 0.25

output:

1

result:

ok ok

Test #2:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

1 0.75

output:

12

result:

ok ok

Test #3:

score: 0
Accepted
time: 3ms
memory: 5808kb

input:

1 0

output:

11111111111111

result:

ok ok

Test #4:

score: -100
Time Limit Exceeded

input:

0.361954 0.578805

output:


result: