Submission #107461

# Submission time Handle Problem Language Result Execution time Memory
107461 2019-04-24T15:18:59 Z tictaccat Type Printer (IOI08_printer) C++14
0 / 100
29 ms 1872 KB
#include <bits/stdc++.h>

using namespace std;

int N;
vector<string> words;

int lcp(string s1, string s2) {
    int i;
    for (i = 0; i < min(s1.size(),s2.size()); i++) {
        if (s1[i] != s2[i]) break;
    }
    return i;
}

int calc(const vector<string> &words) {

    int ops = words[0].size() + 1;

    for (int i = 1; i < N; i++) {
        ops += (int)words[i].size() + words[i+1].size() - lcp(words[i-1],words[i]) + 1;
    }
    
    ops += words[N-1].size();

    return ops;
}

int main() {

    cin >> N;
    for (int i = 0; i < N; i++) {
        string w; cin >> w;
        words.push_back(w);
    }

    sort(words.begin(),words.end());

    cout << calc(words) << "\n";
//    cout << "sort: " << calc(words) << "\n";

    // int minOps = 1e9;

    // do {
    //     minOps = min(minOps,calc(words));
    // } while (next_permutation(words.begin(),words.end()));

    // cout << "exhaust: " << calc(words) << "\n";

    return 0;
}

Compilation message

printer.cpp: In function 'int lcp(std::__cxx11::string, std::__cxx11::string)':
printer.cpp:10:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < min(s1.size(),s2.size()); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 640 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 1020 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 1656 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 1872 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -