| Fişierul intrare/ieşire: | permsort2.in, permsort2.out | Sursă | Lot Baia Mare 2013 - Baraj 3 Seniori |
| Autor | Adrian Panaete, Andrei Grigorean | Adăugată de |  Daniel Constantin Anghel •Magnvs |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Permsort2
Se dă o permutare cu N elemente. Asupra permutării pot fi efectuate două tipuri de mutări:
- Alegerea unui prefix şi inversarea lui.
- Alegerea unui sufix şi inversarea lui.
Vi se cere să sortaţi crescător permutarea folosind operaţiile descrise. Pentru a obţine toate punctele aveţi voie să efectuaţi maximum 2 * N operaţii.
Date de intrare
Fişierul permsort.in conţine pe prima linie numărul N, iar pe următoarea linie N valori reprezentând o permutare.
Date de ieşire
Fişierul de ieşire permsort.out va conţine pe prima linie numărul M de operaţii efectuate. Următoarele M linii vor conţine descrierea operaţiilor efectuate astfel: dacă se doreşte inversarea prefixului care se termină la o anumită poziţie se va afişa caracterul P urmat de valoarea poziţiei, dacă se doreşte inversarea sufixului care se începe la o anumită poziţie se va afişa caracterul S urmat de valoarea poziţiei.
Restricţii
- 1 ≤ N ≤ 100 000
- Dacă M ≤ 2*N veţi obţine punctaj maxim. Dacă 2*N < M ≤ 5*N veţi obţine 50% din punctaj. Pentru M > 5*N nu se vor acorda puncte.
- Pentru 70% din teste N ≤ 50 000
Exemplu
| permsort2.in | permsort2.out |
|---|---|
| 6 6 5 4 1 2 3 | 2 S 4 P 6 |
Explicaţie
După prima operaţie permutarea devine:
6 5 4 3 2 1
A două operaţie inversează tot şirul, iar permutarea devine sortată.
