HSG THPT Hải Phòng 2021 - Bài 3 - VNOJ: VNOI Online Judge

HSG THPT Hải Phòng 2021 - Bài 3

Points: 0.01 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Author:

bedao

Problem source:

Kỳ thi Học sinh giỏi THPT TP Hải Phòng 2021

Problem type

Allowed languages

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~)

Comments

Please read the guidelines before commenting.

-15

quan08 commented on Aug. 27, 2024, 4:39 a.m.

các bạn đừng downvote mình nhé, mà các bạn downvote thì mình cũng kệ:))

This comment is hidden due to too much negative feedback. Show it anyway.

1

kietjumper commented on Oct. 31, 2024, 1:56 a.m.

Kệ thì downvote thui =))

1

nguyen_bui29 commented on July 15, 2024, 1:13 a.m.

Bài này không tìm kiếm nhị phân cũng AC mà ?

0

LumiTech commented on July 10, 2024, 1:18 a.m.

ap dung two sum trong leetcode :))

-1

khanhhoccode commented on May 26, 2024, 4:32 a.m.

này chắc hash table nhỉ

0

duyanhbs2019 commented on April 16, 2024, 10:09 a.m.

sử dụng unordered_map

0

nggiahuy2808008 commented on March 31, 2024, 9:13 a.m.

Dùng 2 con trỏ tốt hơn là dùng tìm kiếm nhị phân =))

0

zackdeaths commented on March 31, 2024, 9:18 a.m.

dùng tknp kiểu gì b , mình chỉ biết làm 2 trỏ

-15

phamvanquyen2522005 commented on Jan. 28, 2024, 7:11 a.m.

include<bits/stdc++.h>

define ll long long

define for1(i,ff,gg) for(ll i=ff;i<=gg;++i)

define for2(i,ff,gg) for(ll i=ff;i>=gg;--i)

define vl vector< ll >

define pb push_back

define fi first

define se second

define ii pair<int ,int>

define PI 3.141592653589793238462643383279502884

const ll maxN=3e5; const ll maxx=1e9+5; using namespace std; ll n,a[maxN],ok=0,k,b[maxN]; map<ll ,vl>mp; ll timkiem(ll a[],ll n,ll k) { ll l=1,r=n; bool ok=false; while(l<=r) { ll m=(l+r)/2; if(a[m]==k) { ok=true; return a[m]; } else if(a[m]<k) { l=m+1; } else r=m-1; } if(ok==false) return maxx; } int main() { #ifdef quyentacaz freopen("pp1.inp", "r", stdin);
freopen("pp1.out", "w", stdout); #endif iosbase::syncwith_stdio(0); cin.tie(NULL); cout.tie(NULL); cin>>n>>k; k=2*k; for1(i,1,n) { cin>>a[i]; b[i]=a[i]; mp[a[i]].pb(i); } sort(a+1,a+n+1); for1(i,1,n) { ll kq=timkiem(a,n,k-b[i]); if(kq!=maxx) { for1(j,0,mp[kq].size()-1) { if(mp[kq][j]!=i) { ok=1; cout<<i<<" "; cout<<mp[kq][j]; return 0; } } } } if(ok==0) { cout<<0<<" "<<0; } return 0;

}

This comment is hidden due to too much negative feedback. Show it anyway.

2

thanhhoang commented on Jan. 23, 2024, 6:52 p.m.

Tìm kiếm nhị phân.