HSG THPT Hải Phòng 2021 - Bài 3
Xem dạng PDF
Gửi bài giải
Điểm:
0,01 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho dãy ~A~ gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ và một số nguyên ~k~.
Hãy tìm hai chỉ số ~p, q~ (~1 \leq p, q \leq n; p \neq q~) sao cho ~\frac{a_p + a_q}{2} = k~.
Input
Dòng 1: Chứa hai số nguyên ~n~ và ~k~.
Dòng 2: Chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~.
Output
Hai chỉ số ~p, q~ tìm được.
Trong trường hợp có nhiều chỉ số ~p, q~ thỏa mãn, chỉ cần in ra một kết quả bất kỳ thỏa mãn. Nếu không tồn tại cặp chỉ số thỏa mãn yêu cầu, ghi ra hai số ~0~.
Các số trên một dòng của kết quả phải ghi cách nhau ít nhất một dấu cách.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~60\%~ | ~n \leq 5000, |k| \leq 10^9, |a_i| \leq 10^9~ |
| 2 | ~20\%~ | ~5000 \leq n \leq 10^5, |k| \leq 10^5, |a_i| \leq 10^5~ |
| 3 | ~20\%~ | ~5000 \leq n \leq 10^5, |k| \leq 10^9, |a_i| \leq 10^9~ |
Sample Input 1
6 4
1 3 2 5 8 6
Sample Output 1
2 4
Sample Input 2
3 5
1 3 2
Sample Output 2
0 0
Notes
Trong ví dụ thứ nhất, có nhiều bộ chỉ số (~p; q~) thỏa mãn điều kiện đề bài như:
(~2; 4~)
(~4; 2~)
(~3; 6~)
(~6; 3~)
Bình luận
yêu admin số 1 tioi
include<bits/stdc++.h>
define ll long long
define N int(1e6)
using namespace std; int a[N+2]; map<int,int> m; int main(){ iosbase::syncwith_stdio(0);cin.tie(0);cout.tie(0); int n,k; cin>>n>>k; for (int i=1;i<=n;i++){ cin>>a[i]; } for (int i=1;i<=n;i++){ int s=2*k-a[i]; if (m[s]!=0){ cout<<m[s]<<" "<<i; return 0; } m[a[i]]=i; } cout<<"0 0"; return 0; }
Mình tạo 1 struct lưu vị trí và giá trị, sau đó sort và dùng two pointers.
bài này ta có thể lưu chỉ số của dãy a thành 1 ma trận sau đó ta sắp xếp chúng lại rồi dùng 2 con trỏ
dùng dict nhanh hơn nhé
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Kệ thì downvote thui =))
Bài này không tìm kiếm nhị phân cũng AC mà ?
ap dung two sum trong leetcode :))
này chắc hash table nhỉ
sử dụng unordered_map
Dùng 2 con trỏ tốt hơn là dùng tìm kiếm nhị phân =))
dùng tknp kiểu gì b , mình chỉ biết làm 2 trỏ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Tìm kiếm nhị phân.