Submission #1026278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026278		Zicrus	Type Printer (IOI08_printer)	C++17	20 / 100	1075 ms	1372 KiB

printer

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

typedef long long ll;

vector<string> w;

ll dist(string a, string b) {
    int firstDiff = 0;
    while (firstDiff < a.size() && firstDiff < b.size() && a[firstDiff] == b[firstDiff]) firstDiff++;
    return a.size() + b.size() - 2 * firstDiff;
}

pair<ll, vector<string>> state(string str, ll mask) {
    if (mask >= (1 << w.size()) - 1) return {0, vector<string>(1, str)};
    ll mn = 1ll << 62;
    vector<string> h;
    for (int i = 0; i < w.size(); i++) {
        if (mask & (1 << i)) continue;
        ll dst = dist(str, w[i]);
        auto st = state(w[i], mask | (1 << i));
        if (dst + st.first < mn) {
            mn = dst + st.first;
            h = st.second;
        }
    }
    h.push_back(str);
    return {mn, h};
}

void solve() {
    ll n;
    cin >> n;
    w = vector<string>(n);
    for (auto &e : w) cin >> e;
    auto st = state("", 0);
    cout << (st.first + w.size()) << '\n';
    vector<char> buf;
    reverse(st.second.begin(), st.second.end());
    for (auto &e : st.second) {
        if (e.size() == 0) continue;
        int firstDiff = 0;
        while (firstDiff < e.size() && firstDiff < buf.size() && e[firstDiff] == buf[firstDiff]) firstDiff++;
        while (buf.size() > firstDiff) {
            cout << "-\n";
            buf.pop_back();
        }
        for (int i = buf.size(); i < e.size(); i++) {
            cout << e[i] << '\n';
            buf.push_back(e[i]);
        }
        cout << "P\n";
    }
}

int main() {
    solve();
}

Compilation message (stderr)

printer.cpp: In function 'll dist(std::string, std::string)':
printer.cpp:10:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     while (firstDiff < a.size() && firstDiff < b.size() && a[firstDiff] == b[firstDiff]) firstDiff++;
      |            ~~~~~~~~~~^~~~~~~~~~
printer.cpp:10:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     while (firstDiff < a.size() && firstDiff < b.size() && a[firstDiff] == b[firstDiff]) firstDiff++;
      |                                    ~~~~~~~~~~^~~~~~~~~~
printer.cpp: In function 'std::pair<long long int, std::vector<std::__cxx11::basic_string<char> > > state(std::string, ll)':
printer.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < w.size(); i++) {
      |                     ~~^~~~~~~~~~
printer.cpp: In function 'void solve()':
printer.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         while (firstDiff < e.size() && firstDiff < buf.size() && e[firstDiff] == buf[firstDiff]) firstDiff++;
      |                ~~~~~~~~~~^~~~~~~~~~
printer.cpp:43:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         while (firstDiff < e.size() && firstDiff < buf.size() && e[firstDiff] == buf[firstDiff]) firstDiff++;
      |                                        ~~~~~~~~~~^~~~~~~~~~~~
printer.cpp:44:27: warning: comparison of integer expressions of different signedness: 'std::vector<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         while (buf.size() > firstDiff) {
      |                ~~~~~~~~~~~^~~~~~~~~~~
printer.cpp:48:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int i = buf.size(); i < e.size(); i++) {
      |                                  ~~^~~~~~~~~~

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