स्थिर छँटाई
कुछ छँटाई एल्गोरिदम उन आइटमों के बीच का क्रम बनाए रखते हैं जिनके सॉर्ट कुंजी (sort key) समान होती है। ऐसे मामलों में, हम कहते हैं कि एल्गोरिदम स्थिर छँटाई (stable sorting) करता है।
कल्पना कीजिए कि हम ऐरे में मौजूद संख्याओं को उनके शुरुआती इंडेक्स के साथ लिखते हैं, ताकि छँटाई के बाद हम देख सकें कि प्रत्येक तत्व कहाँ खिसक गया है।
Initial array | (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) |
जब स्थिर छँटाई की जाती है, तो एल्गोरिदम उन आइटमों का शुरुआती क्रम बनाए रखता है जो आपस में बराबर हैं। वहीं, अस्थिर छँटाई (unstable sorting) के मामले में यह क्रम बदल भी सकता है।
चुनौती
मान लीजिए कि आपके पास n की संख्या वाले प्रारंभिक पूर्णांकों का एक ऐरे है: और n इंडेक्स: । आपको एक नई ऐरे बनानी है जिसका पहला तत्व , दूसरा इत्यादि होगा, यानी दिए गए इंडेक्सों के क्रम में तत्व लिए जाएंगे।
इसके बाद आपको जाँचना है कि प्राप्त हुआ ऐरे, प्रारंभिक ऐरे का स्थिर छँटा हुआ संस्करण है या नहीं।
इनपुट
इनपुट की पहली पंक्ति में एक मात्र पूर्णांक n (1 ≤ n ≤ ) दिया जाता है।
अगली पंक्ति में n स्पेस से अलग किए हुए पूर्णांक दिए जाते हैं ( ≤ ≤ )।
उसके बाद की पंक्ति में n स्पेस से अलग किए हुए इंडेक्स (0 ≤ < n) दिए जाते हैं।
आउटपुट
यदि इंडेक्सों का दिया गया क्रम पर स्थिर छँटाई के परिणामस्वरूप प्राप्त होने वाले क्रम से मेल खाता है, तो प्रोग्राम को “Yes” मुद्रित करना चाहिए; अन्यथा “No” मुद्रित करना चाहिए।
उदाहरण
Input | Output |
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