oj.uz

Submission #1109766

# Submission time Handle Problem Language Result Execution time Memory
1109766 2024-11-07T14:04:53 Z Lakshya108 Type Printer (IOI08_printer) C++17
10 / 100
 446 ms 2180 KB 
#include <bits/stdc++.h>
using namespace std;

void min_operations_to_print(vector<string>& words) {
    // Sort the words lexicographically to maximize reuse of common prefixes
    sort(words.begin(), words.end());
    
    string current_word = "";  // Tracks the current word on the printer
    vector<char> operations;   // Stores the sequence of operations
    
    for (const string& word : words) {
        // Find the longest common prefix length between current_word and word
        int common_length = 0;
        while (common_length < current_word.size() && 
               common_length < word.size() && 
               current_word[common_length] == word[common_length]) {
            ++common_length;
        }
        
        // Remove characters beyond the common prefix in the current word
        for (int i = current_word.size(); i > common_length; --i) {
            operations.push_back('-');  // Remove the last letter
        }
        
        // Add the remaining characters of the target word after the common prefix
        for (int i = common_length; i < word.size(); ++i) {
            operations.push_back(word[i]);  // Add each letter to match the target word
        }
        
        // Print the word after it's fully formed
        operations.push_back('P');  // Print operation
        
        // Update the current word to the last printed word
        current_word = word;
    }
    
    // Output the number of operations and the operations themselves
    cout << operations.size() << endl;
    for (char op : operations) {
        cout << op << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    
    vector<string> words(N);
    for (int i = 0; i < N; ++i) {
        cin >> words[i];
    }
    
    min_operations_to_print(words);
    return 0;
}

Compilation message

printer.cpp: In function 'void min_operations_to_print(std::vector<std::__cxx11::basic_string<char> >&)':
printer.cpp:14:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         while (common_length < current_word.size() &&
      |                ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
printer.cpp:15:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |                common_length < word.size() &&
      |                ~~~~~~~~~~~~~~^~~~~~~~~~~~~
printer.cpp:26:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int i = common_length; i < word.size(); ++i) {
      |                                     ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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