Submission #1091514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091514		nguyen31hoang08minh2003	Cezar (COCI16_cezar)	C++17	30 / 100	1 ms	604 KiB

cezar

/*
     +------------------------------------------------------------------------------------+
     |//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\|
     |/+---------+---------+------------+-----+-----------------------------------+-----+\|
     |\|//     \\|//     \\|//   /\   \\|// \\|//    _______________            \\|// \\|/|
     |/|/       \|/ Clock \|/   //\\   \|/   \|/    /###############\            \|/   \|\|
     |\| S M 7 2 |\       /|    //\\    |  T  |    /#################\            |  T  |/|
     |/| a a t 0 |\\_____//|   ///\\\   |  h  |   /-------------------\           |  h  |\|
     |\| t y h 2 +---------+  ////\\\\  |  e  |    |__   __   __   __|      ___   |  e  |/|
     |/| u     2 |//     \\|   ///\\\   |     |    /##\ /##\ /##\ /##\______|=|   |     |\|
     |\| r       |/ 11:00 \|  ////\\\\  |  T  |    |[]   []   []   []|######\=|   |  H  |/|
     |/| d       |\       /| /////\\\\\ |  r  |    |==   ==   ==   ==|#######\|   |  o  |\|
     |\| a       |\\_____//|  ////\\\\  |  e  |    +-----------------+--------\   |  u  |/|
     |/| y       +---------+ /////\\\\\ |  e  |    |__    _____    __|________|   |  s  |\|
     |\|         |//     \\|//////\\\\\\|     |    /##\  /#####\  /##\|______||   |  e  |/|
     |/|         |/  UTC  \|     ||     |     |    |[]   |__|__|   []||______||   |     |\|
     |\|\       /|\  +07  /|\    ||    /|\   /|\   |==   |__|__|   ==||______||  /|\   /|/|
     |/|\\_____//|\\_____//|\\___||___//|\\_//|\\__|_____|__|__|_____||______||_//|\\_//|\|
     |\+---------+---------+------------+-----+-----------------------------------+-----+/|
     |\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//|
     +------------------------------------------------------------------------------------+

*/
#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) int((x).size())

template<class A, class B>
bool minimize(A &a, const B& b) {
    return a <= b ? false : (a = b, true);
}

template<class A, class B>
bool maximize(A &a, const B& b) {
    return a >= b ? false : (a = b, true);
}

template<class X, class Y>
std::ostream& operator << (std::ostream& outputStream, const std::pair<X, Y> &p) {
    return outputStream << '{' << p.first << ", " << p.second >> '}';
}

template<class T>
std::ostream& operator << (std::ostream& outputStream, const std::vector<T>& values) {
    outputStream << '{';
    for (const T& value : values)
        outputStream << value << ' ';
    return outputStream << '}';
}

using namespace std;

const int MAX_N = 105;

signed main() {
    int n, a[MAX_N]{}, lengths[MAX_N]{}, deg[270]{};
    string order, words[MAX_N];
    vector<char> adj[270];
    char result[270]{};
    queue<char> q;
    const function<void(void)> outputNE = []() {
        cout << "NE\n";
        exit(0);
    };
//    freopen("input.INP", "r", stdin);
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> words[i];
        lengths[i] = words[i].size();
    }
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        --a[i];
    }
    for (int i = 1, j, length; i < n; ++i) {
        length = min(lengths[a[i - 1]], lengths[a[i]]);
        for (j = 0; j < length; ++j)
            if (words[a[i - 1]][j] != words[a[i]][j]) {
                adj[words[a[i - 1]][j]].push_back(words[a[i]][j]);
                ++deg[words[a[i]][j]];
                length = -1;
                break;
            }
        if (length >= 0 && lengths[a[i - 1]] > lengths[a[i]])
            outputNE();
    }
    for (char c = 'a'; c <= 'z'; ++c)
        if (!deg[c])
            q.push(c);
    for (; !q.empty(); q.pop()) {
        const char &u = q.front();
        order += u;
        for (const char &v : adj[u])
            if (!(--deg[v]))
                q.push(v);
    }
    if (order.size() != 26)
        outputNE();
    cout << "DA\n";
    for (int i = 0; i < 26; ++i)
        result[order[i]] = 'a' + i;
    result['z' + 1] = 0;
    cout << result + 'a' << '\n';
    return 0;
}

Compilation message (stderr)

cezar.cpp: In function 'int main()':
cezar.cpp:81:39: warning: array subscript has type 'char' [-Wchar-subscripts]
   81 |                 adj[words[a[i - 1]][j]].push_back(words[a[i]][j]);
      |                                       ^
cezar.cpp:82:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   82 |                 ++deg[words[a[i]][j]];
      |                                     ^
cezar.cpp:90:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   90 |         if (!deg[c])
      |                  ^
cezar.cpp:95:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   95 |         for (const char &v : adj[u])
      |                                  ^
cezar.cpp:96:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   96 |             if (!(--deg[v]))
      |                         ^
cezar.cpp:103:24: warning: array subscript has type 'char' [-Wchar-subscripts]
  103 |         result[order[i]] = 'a' + i;
      |                        ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10