Facebook Hacker Cup 2017 Round 3 A

salient_strings.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>

using namespace std;

int main()
{
    int T;
    cin>>T;
    for (int test=1; test<=T; test++)
    {
        int N;
        cin>>N;
        vector<int> P(N);
        for (int &p: P)
            cin>>p,
            p--;

        P.push_back(-1);
        vector<int> X(N);
        for (int i=0; i<N; i++)
            X[P[i]] = i;
        
        vector<int> A(N);
        int a = 0;
        for (int i=1; i<N; i++)
        {
            if (P[X[i]+1] < P[X[i-1]+1])
                a++;
            A[i] = a;
        }

        string ans = "";
        for (int i=0; i<N; i++)
            ans += char('A'+A[P[i]]);
        bool ok = true;
        for (char c: ans)
            if (c<'A' || 'Z'<c)
                ok = false;
        printf("Case #%d: %s\n", test, ok ? ans.c_str() : "-1");
    }
}