4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Есеп В. AB

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

A,B сыныптарынан $N$ оқушы бір қатарда тұр. $i$-ші тұрған оқушы, оның сол жағында $c_i$ оқушы оның сыныбынан емес екенің айтты. Сізге $c$ массивіндегі сандарды араластырып береді. Кез келген оқушылардың орналасу тәртібің табыңыз.

Формат входного файла

Бірінші жолда бір бүтін сан $N(1 <= N <= 1.5\cdot 10^6)$. Екінші жолда $N$ бүтін сан $x_1,x_2,...,x_N(0 <= x_i <= N)$ — $c$ массивын араластырылуы.

Формат выходного файла

Оқушылардың бастапқы орналасу тәртібің $a$ жәңе $b$ символынын тұратын, ұзындығы $N$ болатын сөз ретінде шығарыңыз. Егер бірнеше мүмкін дұрыс жауап болса, кез келгенің шығарыңыз.

Система оценки

Есеп $9$ бөлімнен тұрады:

1. Берілгеніндегі мысал. $0$ ұпайға бағаланады.
2. $N <= 10^5$. B сыныбынан бірде бір оқушы болмайтындай жауабы бар. $6$ ұпайға бағаланады.
3. $N <= 20$. $10$ ұпайға бағаланады.
4. $N <= 10^5$. B сыныбынан 2 оқушыдан көп болмайтындай жауабы бар. $8$ ұпайға бағаланады.
5. $N <= 10^5$. $c$ массивы $x$ массивына орын араластырмай тең болатын оқушылардың орналасу тәртібі бар. $14$ ұпайға бағаланады.
6. $N <= 40$. $13$ ұпайға бағаланады.
7. $N <= 2000$. $10$ ұпайға бағаланады.
8. $N <= 300000$. $27$ ұпайға бағаланады.
9. $N <= 1500000$. $12$ ұпайға бағаланады.

Примеры:

Вход

4
1 0 2 0

Ответ

bbab

Вход

5
0 0 2 1 3

Ответ

bbaba

Замечание

Егер $bbab$ бастапқы орналасу тәртібі болса, онда $c_1 = 0, c_2 = 0, c_3 = 2, c_4 = 1$ болады. Араластыру арқылы [1,0,2,0] массивін алуға болады. ( Temirlan Satylkhanov )