oj.uz

Submission #963161

# Submission time Handle Problem Language Result Execution time Memory
963161 2024-04-14T15:57:28 Z ByeWorld Type Printer (IOI08_printer) C++14
100 / 100
 78 ms 39928 KB 
#include <bits/stdc++.h>
#include <random>
#define ll long long
// #define int long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 5e5+10;
const int MAXA = 1e6+10;
const int INF = 2e9+10;
const int LOG = 30;
const int MOD = 998244353;

int n;
string s[MAXN], gan[MAXN];
vector <pair<char,char>> vec;
vector <pair<string, int>> out;
vector <char> ANS;

signed main(){
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	int mx = -1, idx = -1;
	for(int i=1; i<=n; i++){
		cin >> s[i];
		if(mx < (int)s[i].size()){
			mx = (int)s[i].size();
			idx = i;
		}
	}
	for(int i=0; i<s[idx].size(); i++){
		pair<char,char> te = {s[idx][i], 'z'}; 
		vec.pb(te);
	}
	for(int i=1; i<=n; i++){
		gan[i] = s[i];
		for(int j=0; j<min(vec.size(), s[i].size()); j++){
			if(s[i][j] == vec[j].fi) gan[i][j] = vec[j].se;
			else if(s[i][j] == vec[j].se) gan[i][j] = vec[j].fi;
		}
		// cout << i << ' ' << gan[i] << " pp\n";
		out.pb({gan[i], i});
	}
	sort(out.begin(), out.end());
	// for(auto in : out){
	// 	cout << in.fi << ' ' << in.se << " inn\n";
	// }
	string nw = "";
	for(int i=0; i<n; i++){
		int idx = out[i].se;
		string mau = s[idx];
		while(mau != nw){
			int len = nw.size();
			if(len==0){
				nw.pb(mau[0]);
				ANS.pb(mau[0]);
			} else {
				bool can = 1;
				for(int i=0; i<len; i++){
					if(nw[i] != mau[i]){
						nw.pop_back();
						ANS.pb('-');
						can = 0;
					}
				}
				if(can){
					nw.pb(mau[len]);
					ANS.pb(mau[len]);
				}
			}
		}
		ANS.pb('P');
	}

	cout << ANS.size() << '\n';
	for(auto in : ANS) cout << in << '\n';
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i=0; i<s[idx].size(); i++){
      |               ~^~~~~~~~~~~~~~
printer.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   44 |   for(int j=0; j<min(vec.size(), s[i].size()); j++){
      |                ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31580 KB Output is correct
2 Correct 7 ms 31580 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31580 KB Output is correct
2 Correct 9 ms 31576 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31580 KB Output is correct
2 Correct 7 ms 31580 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 32088 KB Output is correct
2 Correct 8 ms 31580 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31904 KB Output is correct
2 Correct 8 ms 31580 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31832 KB Output is correct
2 Correct 9 ms 31836 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 32088 KB Output is correct
2 Correct 17 ms 32692 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 32860 KB Output is correct
2 Correct 19 ms 33136 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 34540 KB Output is correct
2 Correct 74 ms 38828 KB Output is correct
3 Correct 49 ms 37380 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 34080 KB Output is correct
2 Correct 74 ms 39928 KB Output is correct
3 Correct 55 ms 38112 KB Output is correct
4 Correct 78 ms 39684 KB Output is correct