Կայուն տեսակավորում (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