Fişierul intrare/ieşire:permsort2.in, permsort2.outSursăLot Baia Mare 2013 - Baraj 3 Seniori
AutorAdrian Panaete, Andrei GrigoreanAdăugată deMagnvsDaniel Constantin Anghel Magnvs
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inpermsort2.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ă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content