Submission #981739

#	Time	Username	Problem	Language	Result	Execution time	Memory
981739		zzodiqus	Type Printer (IOI08_printer)	C++17	20 / 100	59 ms	38644 KiB

printer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define FAST ios_base::sync_with_stdio(false), cin.tie(NULL) , cout.tie(NULL)
#define endl "\n"
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpii vector<pair<int , int> >
#define vc vector<char>
#define vvc vector<vector<char> >
#define mii map<int , int>
#define pii pair<int , int>
#define vb vector<bool>
#define vvb vector<vector<bool> >
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define fr(i,n) for(int i=0; i<(n); i++)
#define dbg(var) cout<<#var<<" : "<<var<<"\n"
#define all(v) v.begin(),v.end()
#define srt(v)  sort(v.begin(),v.end())         // sort 
#define mxe(v)  *max_element(v.begin(),v.end())     // find max element in vector
#define mne(v)  *min_element(v.begin(),v.end())     // find min element in vector
#define unq(v)  v.resize(distance(v.begin(), unique(v.begin(), v.end())));
// make sure to sort before applying unique // else only consecutive duplicates would be removed 
#define bin(x,y)  bitset<y>(x) 

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define set_bits(x) __builtin_popcountll(x)  // number of set bits
#define first_set(x) __builtin_ctzll(x)      // ...001000 -> 3 
#define last_set(x) __builtin_ctzll(x)       // 00010000 00000000 00000000 00000000 -> 3 (for 32 bit int), not very useful tho

using namespace std;
const int MOD=1e9+7;      // Hardcoded, directly change from here for functions!

// using namespace __gnu_pbds;
using __gnu_pbds::tree;
using __gnu_pbds::rb_tree_tag;
using __gnu_pbds::tree_order_statistics_node_update;
using __gnu_pbds::null_type;

// _GLIBCXX_DEBUG must not be defined otherwise some internal check will fail
#undef _GLIBCXX_DEBUG

template <typename K, typename V, typename Comp = less<K>>
using indexed_map = tree<K, V, Comp, rb_tree_tag, tree_order_statistics_node_update>;

template <typename K, typename Comp = less<K>>
using indexed_set = indexed_map<K, null_type, Comp>;

// ¡¡IMPORTANT!! (for using less_equals<K>)
// using less_equals<K> makes lower_bound works as upper_bound and vice-versa
// for erase use: any.erase(any.find_by_order(any.order_of_key(val)));
// don't use .find() because it will always return .end()
template <typename K, typename V, typename Comp = less_equal<K>>
using indexed_multimap = indexed_map<K, V, Comp>;

template <typename K, typename Comp = less_equal<K>>
using indexed_multiset = indexed_map<K, null_type, Comp>;

// find_by_order(k): returns an iterator to the (k+1)-th largest element (0-based)
// order_of_key(num):  #elements in the set strictly smaller "num"

void modadd(int &a , int b) {a=((a%MOD)+(b%MOD))%MOD;}
void modsub(int &a , int b) {a=((a%MOD)-(b%MOD)+MOD)%MOD;}
void modmul(int &a , int b) {a=((a%MOD)*(b%MOD))%MOD;}
// ================================== take ip/op like vector,pairs directly!==================================
template<typename typC,typename typD> istream &operator>>(istream &cin,pair<typC,typD> &a) { return cin>>a.first>>a.second; }
template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (auto &x:a) cin>>x; return cin; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const pair<typC,typD> &a) { return cout<<a.first<<' '<<a.second; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const vector<pair<typC,typD>> &a) { for (auto &x:a) cout<<x<<'\n'; return cout; }
template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
template<typename typC> ostream &operator<<(ostream &cout,const set<typC> &a) { for (auto it:a) cout<<it << " "; return cout; }
template<typename typC> ostream &operator<<(ostream &cout,const multiset<typC> &a) { for (auto it:a) cout<<it << " "; return cout; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const map<typC , typD> &m) { for (auto it:m) cout<<it.ff << " : " << it.ss << endl; return cout; }
// ===================================END Of the input module ==========================================

const int W = 5e5 + 5;
int trie[26][W]; 
int node_cnt;
int en[W];

void add(string s){
	int n = s.size();
	int x = 0; // root
	for(int i=0;i<s.size();i++){
		int cur = s[i]-'a';
		if(trie[cur][x] == 0){
			trie[cur][x] = ++node_cnt;
		}
		x = trie[cur][x];
	}
	en[x] += 1;
}

int height[W];

void dfs1(int u , int h){
	for(int i=0;i<26;i++){
		if(trie[i][u] != 0){
			int v = trie[i][u];
			dfs1(v , h+1);
			height[u] = max(height[u] , 1+height[v]);
		}
	}
}

string ans;

void dfs(int u , string &s){
	if(en[u] != 0){
		// end of a word
		ans += 'P';
	}

	vvi choices;
	for(int i=0;i<26;i++){
		if(trie[i][u] != 0){
			int v = trie[i][u];
			int kk = height[v];
			choices.pb({kk , v , i});
		}
	}

	srt(choices);
	reverse(all(choices));
	fr(i,choices.size()){
		char add = 'a' + choices[i][2];
		ans += add;
		s += add;
		dfs(choices[i][1] , s);
	}

	ans += '-';
	s.pop_back();
}

void solve(){
    int n;
    cin >> n;
    
    fr(i,n){
    	string s;
    	cin >> s;
    	add(s);
    }

	// do a dfs on the trie created 
	string temp = "";
	dfs(0 , temp);

	while(ans.back() == '-')ans.pop_back();
	cout << ans.size() << endl;
	fr(i,ans.size())cout << ans[i] << endl;
}

int32_t main()
{
    FAST;

    int T=1;
    // cin >> T;
    for (int cas=1;cas<=T;cas++)
    {
        // cout << "Case #" << case << ": " << endl;
        solve();

        // if(case == _){
        //  int n;
        //  cin >> n;
        //  vi a(n);
        //  cin >> a;
        //  cout << n << "_";
        //  fr(i,n)cout << a[i] << "_";
        // }
        // else solve();
    }
    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void add(std::string)':
printer.cpp:90:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~
printer.cpp:88:6: warning: unused variable 'n' [-Wunused-variable]
   88 |  int n = s.size();
      |      ^
printer.cpp: In function 'void dfs(long long int, std::string&)':
printer.cpp:20:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define fr(i,n) for(int i=0; i<(n); i++)
      |                               ^
printer.cpp:131:2: note: in expansion of macro 'fr'
  131 |  fr(i,choices.size()){
      |  ^~
printer.cpp: In function 'void solve()':
printer.cpp:20:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define fr(i,n) for(int i=0; i<(n); i++)
      |                               ^
printer.cpp:158:2: note: in expansion of macro 'fr'
  158 |  fr(i,ans.size())cout << ans[i] << endl;
      |  ^~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10