Ալգորիթմներ և Տվյալների Կառուցվածքներ

Կայուն տեսակավորում (Stable sorting)

Որոշ տեսակավորման ալգորիթմներ պահպանում են այն տարրերի նախնական դասավորությունը, որոնց արժեքները հավասար են։ Այդ դեպքերում ասում ենք, որ ալգորիթմը կատարում է կայուն տեսակավորում:

Պատկերացրեք, որ զանգվածի թվերն ու դրանց նախնական ինդեքսները գրենք միասին, որպեսզի տեսակավորումից հետո տեսնենք, թե որտեղ են տարրերը հասել:

Սկզբնական զանգված

(10, 0)

(12, 1)

(10, 2)

(7, 3)

(-3, 4)

(-3, 5)

(7, 6)

Կայուն տեսակավորում

(-3, 4)

(-3, 5)

(7, 3)

(7, 6)

(10, 0)

(10, 2)

(12, 1)

Ոչ կայուն տեսակավորում

(-3, 5)

(-3, 4)

(7, 3)

(7, 6)

(10, 2)

(10, 0)

(12, 1)

Կայուն տեսակավորում կատարելիս, եթե որևէ երկու տարրեր հավասար են, ալգորիթմը պահպանում է դրանց նախնական հերթականությունը։ Իսկ ոչ կայուն տեսակավորման դեպքում սկզբնական հերթականությունը կարող է փոխվել:

Առաջադրանք

Տրված է n ամբողջ թվերից կազմված զանգված , ինչպես նաև n ինդեքսներ ։ Պետք է ստեղծել նոր զանգված վերցնելով տարրերը տրված ինդեքսների հերթականությամբ: Այն է, նոր զանգվածի առաջին էլեմենտը կլինի , երկրորդը և այդպես շարունակ:

Ձեզ խնդրում են ստուգել, թե արդյոք ստացված զանգվածը համապատասխանում է սկզբնական զանգվածի կայուն տեսակավորված տարբերակին:

Մուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ )։

Հաջորդ տողում գրված են n ամբողջ թվեր ( ≤ ≤ ):

Հաջորդ տողում գրված են n ամբողջ ինդեքսներ (0 ≤ < n):

Ելք

Ծրագիրը պետք է տպի Yes, եթե տրված ինդեքսների հերթականությունը կարող էր առաջանալ կայուն տեսակավորումից, հակառակ դեպքում՝ No:

Օրինակներ

Մուտք

Ելք

8
10 12 10 7 -3 4 -3 5
4 6 5 7 3 0 2 1

Yes

8
10 12 10 7 -3 4 -3 5
6 4 5 7 3 2 0 1

No

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue