All Tracks Problem

Ashwathama
Tag(s):

Medium, Trie, cascading

Problem
Editorial
Analytics

Ganesh Gaitonde has been convinced that he is Ashwathama ( invincible ). He now wants to do daring things in life. He is now using his own number system, Gaitonde System in Gopalmath. All the number in Gaitonde's system have 9 digits. In Gaitonde's system, he can change the priority of a digit.

Let's take an array A = [000000003,000000002,000000022,000000033]

Initially, the priority of digits are as follows: 0<1<2<3<4<5<6<7<8<9

sorted array B = [000000002,000000003,000000022,000000033]

after interchanging the priority of digits 2 and 3,

priority of digits: 0<1<3<2<4<5<6<7<8<9

sorted array B = [000000003,000000002,000000033,000000022]

after interchanging the priority of digits 0 and 9,

priority of digits: 9<1<3<2<4<5<6<7<8<0

sorted array B = [000000033,000000032,000000003,000000002]

 You are given two types of queries:

Type 0: 0 k - find the kth element of Array A if elements are sorted according to current priority of digits.

Type 1: 1 L R - Interchange the priority of digits L and R

Input Format : 

  • The first line of input contains N and Q, the length of the Array A and Number of queries.
  • The second line of input contains N elements each of length 9 digits of the array A.
  •  Next, Q lines of input contain a query of the format described above.

Output Format :

  • For each query of type 0, print kth element after sorting the array according to priority in new line.

Constraints :

  • \(1 \le N,Q \le 10^{5}\)
  • \(1 \le K \le N\)
  • \(0 \le L,R \le 9\)
SAMPLE INPUT
4 5
000000003 000000002 000000022 000000033
0 1
1 2 3
0 1
1 0 9
0 1
SAMPLE OUTPUT
000000002
000000003
000000033
Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

NIT Surat

Challenge Name

EPIPHANY 8.0

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?