oj.uz

Submission #159703

# Submission time Handle Problem Language Result Execution time Memory
159703 2019-10-24T02:50:03 Z silxikys Cezar (COCI16_cezar) C++14
30 / 100
 3 ms 376 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -