Submission #963161

#	Time	Username	Problem	Language	Result	Execution time	Memory
963161		ByeWorld	Type Printer (IOI08_printer)	C++14	100 / 100	78 ms	39928 KiB

printer

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10