CSES - Sum of Two Values | Tổng hai giá trị
Xem PDF
Đ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
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";
}
4 bình luận nữa