CSES - Sum of Two Values | Tổng hai giá trị - LQDOJ: Le Quy Don Online Judge

CSES - Sum of Two Values | Tổng hai giá trị

Tác giả:

Dạng bài

Điểm: 900 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho một mảng gồm \(n\) số nguyên và nhiệm vụ của bạn là tìm hai giá trị (tại các vị trí phân biệt) có tổng là \(x\).

Input

Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước mảng và tổng mong muốn.
Dòng thứ hai có \(n\) số nguyên \(a_1,a_2,\ldots,a_n\): các giá trị của mảng.

Output

In hai số nguyên: vị trí của các giá trị. Nếu có một số lời giải, bạn có thể in bất kỳ lời giải nào trong số đó. Nếu không có lời giải nào, in IMPOSSIBLE.

Constraints

\(1 \leq n \leq 2 \cdot 10 ^ 5\)
\(1 \leq x, a_i \leq 10 ^ 9\)

Example

Sample input

4 8
2 7 5 1

Sample output

2 4

Bình luận

1

thanhlong2k9 1:09 p.m. 25 Tháng 2, 2024 ← chỉnh sửa 2 →

bài này chỉ cần dùng chặt nhị phân với dùng kiểu pair là ra r:))
mình gửi code của mình mn tham khảo:)))

include <bits/stdc++.h>

define ll long long

define pii pair <ll,ll>

using namespace std;
ll n,x;
pii a[200001];
int search(ll l,ll r, ll x)
{
ll ans=-1;
while (l<=r)
{
ll mid=(l+r) / 2;
if (a[mid].first==x)
{
ans=mid;
return ans;
}
if (a[mid].first>x) r=mid-1; else l=mid+1;
}
return ans;
}
int main()
{
cin>>n>>x;
for(int i=1;i<=n;i++)
{
cin>>a[i].first;
a[i].second=i;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
ll k=x-a[i].first;
ll vt=search(1,n,k);
if (vt!=-1 && a[i].first+a[vt].first==x && a[i].second!=a[vt].second)
{
if (a[i].second<a[vt].second) cout<<a[i].second<<" "<<a[vt].second; else cout<<a[vt].second<<" "<<a[i].second;
return 0;
}
}
cout<<"IMPOSSIBLE";
}

#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll,ll>
using namespace std;
ll n,x;
pii a[200001];
int search(ll l,ll r, ll x)
{
    ll ans=-1;
    while (l<=r)
    {
        ll mid=(l+r) / 2;
        if (a[mid].first==x)
        {
            ans=mid;
            return ans;
        }
        if (a[mid].first>x) r=mid-1; else l=mid+1;
    }
    return ans;
}
int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].first;
        a[i].second=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        ll k=x-a[i].first;
        ll vt=search(1,n,k);
        if (vt!=-1 && a[i].first+a[vt].first==x && a[i].second!=a[vt].second)
        {
            if (a[i].second<a[vt].second) cout<<a[i].second<<" "<<a[vt].second; else cout<<a[vt].second<<" "<<a[i].second;
            return 0;
        }
    }
    cout<<"IMPOSSIBLE";
}

-1

sondang0914 9:10 p.m. 23 Tháng 10, 2024

ez

4 bình luận nữa