oj.uz

Submission #507412

# Submission time Handle Problem Language Result Execution time Memory
507412 2022-01-12T12:03:14 Z haxorman Type Printer (IOI08_printer) C++14
100 / 100
 79 ms 7144 KB 
    #include <bits/stdc++.h>
    using namespace std;
     
    int32_t main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    	
    	int n;
    	cin >> n;
     
    	vector<string> words(n);
    	for (auto& w : words) {
    		cin >> w;
    	}
     
    	int mx = 0;
    	char c;
    	for (int i = 0; i < n; ++i) {
    		if (mx < words[i].size()) {
    			mx = words[i].size();
    			c = words[i][0];
    		}
    	}
    	
    	vector<pair<int,string>> big;
    	vector<string> smol;
    	for (int i = 0; i < n; ++i) {
    		if (words[i][0] == c) {
    			big.push_back({0, words[i]});
    		}
    		else {
    			smol.push_back(words[i]);
    		}
    	}
    	
    	string extra_big;
    	for (int i = 0; i < big.size(); ++i) {
    		if (big[i].second.size() == mx) {
    			extra_big = big[i].second;
    			break;
    		}
    	}
    	
    	for (int i = 0; i < big.size(); ++i) {
    		int cnt = 0;
    		for (int j = 0; j < big[i].second.size(); ++j) {
    			if (big[i].second[j] == extra_big[j]) {
    				++cnt;
            
    			}
              	else {
                  break;
                }
    		}
    		
    		big[i].first = cnt;
    	}
    	sort(smol.begin(), smol.end());
    	sort(big.begin(), big.end());
    	
    	string cur = "0";
    	vector<char> out;
    	if (smol.size()) {
    		cur = smol[0];
    		for (auto ch : cur) {
    			out.push_back(ch);
    		}
    		out.push_back('P');
     
    		for (int i = 1; i < smol.size(); ++i) {
    			int ind = 0;
    			while (ind < min(cur.size(), smol[i].size()) && 
    				  cur[ind] == smol[i][ind]) {
    				
    				ind++;
    			}
    			ind--;
     
    			int cur_ind = cur.size() - 1;
    			while (cur_ind > ind) {
    				out.push_back('-');
    				cur_ind--;
    			}
     
    			for (int j = ind + 1; j < smol[i].size(); ++j) {
    				out.push_back(smol[i][j]);
    			}
    			out.push_back('P');
     
    			cur = smol[i];
    		}
    	}
    	
    	int start = 0;
    	if (cur[0] == '0') {
    		cur = big[0].second;
    		for (auto ch : cur) {
    			out.push_back(ch);
    		}
    		out.push_back('P');
    		start = 1;
    	}
    	
    	for (int i = start; i < big.size(); ++i) {
    		int ind = 0;
    		while (ind < min(cur.size(), big[i].second.size()) && 
    			  cur[ind] == big[i].second[ind]) {
    			
    			ind++;
    		}
    		ind--;
     
    		int cur_ind = cur.size() - 1;
    		while (cur_ind > ind) {
    			out.push_back('-');
    			cur_ind--;
    		}
     
    		for (int j = ind + 1; j < big[i].second.size(); ++j) {
    			out.push_back(big[i].second[j]);
    		}
    		out.push_back('P');
     
    		cur = big[i].second;
    	}
     
    	cout << out.size() << "\n";
    	for (auto ch : out) {
    		cout << ch << "\n";
    	}
    }

Compilation message

printer.cpp: In function 'int32_t main()':
printer.cpp:18:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |       if (mx < words[i].size()) {
      |           ~~~^~~~~~~~~~~~~~~~~
printer.cpp:36:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::__cxx11::basic_string<char> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |      for (int i = 0; i < big.size(); ++i) {
      |                      ~~^~~~~~~~~~~~
printer.cpp:37:32: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |       if (big[i].second.size() == mx) {
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~
printer.cpp:43:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::__cxx11::basic_string<char> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |      for (int i = 0; i < big.size(); ++i) {
      |                      ~~^~~~~~~~~~~~
printer.cpp:45:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |       for (int j = 0; j < big[i].second.size(); ++j) {
      |                       ~~^~~~~~~~~~~~~~~~~~~~~~
printer.cpp:69:25: 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]
   69 |       for (int i = 1; i < smol.size(); ++i) {
      |                       ~~^~~~~~~~~~~~~
printer.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   71 |        while (ind < min(cur.size(), smol[i].size()) &&
      |               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:84:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |        for (int j = ind + 1; j < smol[i].size(); ++j) {
      |                              ~~^~~~~~~~~~~~~~~~
printer.cpp:103:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::__cxx11::basic_string<char> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |      for (int i = start; i < big.size(); ++i) {
      |                          ~~^~~~~~~~~~~~
printer.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  105 |       while (ind < min(cur.size(), big[i].second.size()) &&
      |              ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:118:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |       for (int j = ind + 1; j < big[i].second.size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~
printer.cpp:27:7: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |       if (words[i][0] == c) {
      |       ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 716 KB Output is correct
2 Correct 9 ms 1224 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1576 KB Output is correct
2 Correct 8 ms 1664 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3348 KB Output is correct
2 Correct 52 ms 6064 KB Output is correct
3 Correct 28 ms 5532 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3156 KB Output is correct
2 Correct 79 ms 7144 KB Output is correct
3 Correct 43 ms 6192 KB Output is correct
4 Correct 47 ms 6920 KB Output is correct