CAGES - Lights, Snakes and Cages
In the zoo there are N cages in which we keep N snakes: each snake in its cage. For experimental reasons, in a month we will move each snake to a different cage: this reordering is given in the input.
Each cage is illuminated by special light, which may be of type A, type B or type C. Your task is to assign the lights A, B, C to the cages so that:
- each snake will change its lighting, i.e. it will be moved to the cage illuminated differently from the cage it currently inhabits;
- lightings are equally distributed, i.e. the number of cages A, the number of cages B and the number of cages C differ by at most one.
Input
The first line contains an integer N (2 ≤ N ≤ 300 000), the number of snakes and cages. Cages are numbered from 1 to N.
Each of the next N lines contains an integer. When K-th of these lines contains the number L, it means that the snake from the cage K will be moved to the cage L (K ≠ L). Two snakes will not move to the same cage.
Output
Print the string composed of the characters A, B and C, such that the K-th character denotes the lighting of the cage K. If there are multiple solutions, print any.
Example
Input: 4 4 3 2 1 Output: ACBC
hide comments
aeon:
2016-09-17 23:00:58
@psetter Kindly have a look at my solution ( id : 17732677 ), I have considered even the cyclic cases, but still I am getting WA after 15 test cases. |
|
avisheksanvas:
2016-07-06 11:15:11
@psetter please check my submission : 17234107!
|
|
codeforsure:
2016-05-22 08:42:18
@author can you please check my submission: 16964085, getting wrong answer after 15 test cases.
|
|
rajatgupta:
2016-04-22 23:12:54
Cant find test cases... getting WA...HELP!!!! |
|
lt:
2016-03-22 17:42:43
5 WAs :( , I'm to figure out what's wrong. Can somebody help me? |
|
Sergio Vieri:
2015-06-14 06:17:02
Solved with 341 lines in Assembly.. yay |
|
kancha:
2014-12-19 11:09:00
well, tried debugging with random case generator, no success :(
|
|
Adrian Satja Kurdija:
2014-08-03 10:11:23
@Bhavik: have you written a random case generator and a checker? I'm sure you'll find your bug that way. |
|
Bhavik:
2014-06-16 18:06:13
@psetter:can you look my id:11776229 and kindly tell if i my approach is right?? Last edit: 2014-06-17 17:23:28 |
|
Adrian Satja Kurdija:
2014-03-28 08:18:14
Many WAs in submissions :) I suggest using random case generator and a checker to find your bugs. |
Added by: | Adrian Satja Kurdija |
Date: | 2014-03-24 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Croatia nationals 2014 (6th grade, 3rd problem "Zmije") |