Submission #159703

#	Time	Username	Problem	Language	Result	Execution time	Memory
159703		silxikys	Cezar (COCI16_cezar)	C++14	30 / 100	3 ms	376 KiB

cezar

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 105;
int n;
string s[N];
vector<int> dir[N];
int deg[30];
int pos[N];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    for (int i = 1; i <= n; i++) {
        int ai; cin >> ai;
        pos[ai] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (pos[i] >= pos[j]) continue;
            //now i comes before j in reordering
            for (int k = 0; k < max(s[i].size(),s[j].size()); k++) {
                if (k == s[i].size()) {
                    //nothing
                    break;
                }
                else if (k == s[j].size()) {
                    //can't be
                    cout << "NE\n";
                    return 0;
                }
                else {
                    if (s[i][k] != s[j][k]) {
                        dir[s[i][k]-'a'].push_back(s[j][k]-'a');
                        deg[s[j][k]-'a']++;
                        break;
                    }
                }
            }
        }
    }
    //debug
    /*
    for (int i = 0; i < 26; i++) {
        cout << (char)(i+'a') << ": ";
        for (int j: dir[i]) {
            cout << (char)(j+'a') << ' ';
        }
        cout << '\n';
    }
    return 0;
    */
    //topsort
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (deg[i] == 0) q.push(i);
    }
    vector<int> ord;
    while (!q.empty()) {
        int f = q.front(); q.pop();
        ord.push_back(f);
        for (int j: dir[f]) {
            if (--deg[j] == 0) {
                q.push(j);
            }
        }
    }
    if (ord.size() != 26) {
        cout << "NE\n";
        return 0;
    }
    else {
        vector<char> ans(26,0);
        for (int i = 0; i < 26; i++) {
            ans[ord[i]] = i+'a';
        }
        cout << "DA\n";
        for (int i = 0; i < 26; i++) {
            cout << ans[i];
        }
        cout << '\n';
    }
}

Compilation message (stderr)

cezar.cpp: In function 'int main()':
cezar.cpp:26:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = 0; k < max(s[i].size(),s[j].size()); k++) {
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cezar.cpp:27:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (k == s[i].size()) {
                     ~~^~~~~~~~~~~~~~
cezar.cpp:31:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 else if (k == s[j].size()) {
                          ~~^~~~~~~~~~~~~~

• 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