Problem: salientstrings (2017 round3)

Many people are avid fans of the daily crossword in the paper, but not you. I
mean, the format is pretty terrible, right? You only get to use English words,
and any hack can look those up in a dictionary. Also, it takes forever to make
just one puzzle. What a waste of time.

You've written a letter to the editor describing a new word game. It's really
easy to make new puzzles because the only thing you give the solver is a
permutation **P1..N** of the first **N** positive integers. It's then up to
the solver to find any string that's _salient_ for the given permutation.

A string is _salient_ for the permutation **P1..N** if it consists of **N**
uppercase letters ("A"..."Z"), such that when its **N** non-empty suffixes are
sorted in lexicographical order, the suffix starting at the _i_th character is
the **Pi**th suffix in the sorted list. It's possible that a given permutation
has no salient strings.

You need some example puzzles to include in your letter. You already have some
permutations generated, so all you need is to supply an answer for each
permutation (if possible).

### Input

Input begins with an integer **T**, the number of different permutations
you've generated. For each permutation, there is first a line containing the
integer **N**. Then **N** lines follow, the _i_th of which contains the
integer **Pi**. It is guaranteed that each integer from 1 to **N** shows up
exactly once in **P**.

### Output

For the _i_th permutation, print a line containing "Case #**i**: " followed by
any salient string for that permutation (note that any valid string consisting
of **N** uppercase letters will be accepted), or "-1" if there are no such
strings.

### Constraints

1 ≤ **T** ≤ 2,000  
1 ≤ **N** ≤ 1,000  
1 ≤ **Pi** ≤ **N**  

### Explanation of Sample

In the first case, if we sort the suffixes of FACEBOOK we get:

  1. ACEBOOK 
  2. BOOK 
  3. CEBOOK 
  4. EBOOK 
  5. FACEBOOK 
  6. K 
  7. OK 
  8. OOK 
If we read the indices of the suffixes back in order of decreasing length, we
get 5 1 3 4 2 8 7 6, which is the given permutation. Therefore "FACEBOOK" is
salient for this permutation, and is one possible accepted answer.



Sample input:
5
8
5
1
3
4
2
8
7
6
5
2
4
5
1
3
9
6
9
3
5
8
2
4
7
1
60
54
17
49
46
60
58
14
55
51
37
11
9
10
44
56
43
36
38
34
33
28
59
26
57
6
48
29
25
12
23
40
45
50
2
20
52
47
16
7
21
1
13
42
22
3
32
35
15
19
39
27
24
8
30
53
31
41
18
4
5
45
35
21
9
44
20
28
24
32
43
18
42
36
1
19
11
7
37
30
39
5
29
34
12
8
40
13
17
10
6
33
45
26
16
3
2
23
25
4
27
22
14
31
41
15
38


Sample output:
Case #1: FACEBOOK
Case #2: FOXEN
Case #3: HUEHUEHUE
Case #4: -1
Case #5: PNEUMONOULTRAMICROSCOPICSILICOVOLCANOCONIOSIS



Code: // Hacker Cup 2017
// Round 3
// Salient Strings
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

int main()
{
	// vars
	int T,t;
	int N;
	int i,c;
	int P[1001],inv[1001];
	char S[1001];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N);
				Fox(i,N)
					Read(P[i]),inv[P[i]]=i;
			P[N]=0;
			// greedy
			printf("Case #%d: ",t);
			c=0;
				Fox1(i,N)
				{
					// determine if the next character up must be used
						if ((i>1) && (P[inv[i]+1]<P[inv[i-1]+1]))
							if ((++c)==26)
							{
								// more than 26 different characters are required
								printf("-1\n");
								goto Done;
							}
					S[inv[i]]=c+'A';
				}
			S[N]='\0';
			printf("%s\n",S);
Done:;
		}
	return(0);
}