oj.uz

Submission #1026278

# Submission time Handle Problem Language Result Execution time Memory
1026278 2024-07-17T18:50:18 Z Zicrus Type Printer (IOI08_printer) C++17
20 / 100
 1000 ms 1372 KB 
#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

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 348 KB Output is correct
2 Correct 86 ms 344 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1041 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 1372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 1368 KB Time limit exceeded
2 Halted 0 ms 0 KB -