Submission #692456

#	Time	Username	Problem	Language	Result	Execution time	Memory
692456		Litusiano	Type Printer (IOI08_printer)	C++14	100 / 100	243 ms	96608 KiB

printer

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
 
//#define int long long
#define f first
#define s second
#define ii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvii vector<vector<ii>>
#define pb push_back
#define vpi vector<ii> 
#define forcin for(int i = 0; i<n; ++i) cin>>v[i];
#define pq priority_queue<ii>
#define mp make_pair
#define ld long double
#define vc vector<char>
#define vvc vector<vc>
#define vb vector<bool>
#define vvb vector<vb>
#define all(a) (a).begin(),(a).end()
#define For(i, n, x) for (int i = x; i < n; i++)
#define rsz(a,x) assign(a,x)
#define endl "\n"
int n;
 
struct Node{
  unordered_map<char,Node*> son;
  bool aca = 0;
};
 
void add(Node* Trie, string& x, int i){
  if(i == x.size()){
    Trie -> aca = 1;
    return;
  }
  if(Trie -> son.find(x[i]) == Trie -> son.end()){
    // creo el Node del Nou caracter,

    Trie-> son[x[i]] = new Node;    
  }
  add(Trie->son[x[i]],x,i+1);
}
int pc = 0;
string mxs = "";
// La ultima paraula es la mes llarga
vc ans;
void dfs1(Node* u, int d, bool MX){
  //cerr<<d<<" "<<mxs.size()<<endl;
  //Processo mxs la ultima, per tant MX es si nomes si es el mxs
  if(u->aca){
    pc++; ans.pb('P');
  }
  bool f = false;
  for(auto x : u->son){
    if(MX && x.f == mxs[d]){
      f = 1;
      continue;
    }
    ans.pb(x.f);
    dfs1(x.s,d+1,0);
    if(pc!=n) ans.pb('-');
  }
  if(MX && f){
    ans.pb(mxs[d]);
    dfs1(u->son[mxs[d]],d+1,1);
    if(pc!=n) ans.pb('-');
  }

}
 
signed main(){
 
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n;
  Node* st = new Node;
  For(i,n,0){
    string x; cin>>x;
    if(x.size() > mxs.size()) mxs = x;
    add(st,x,0);
  }
  // Exploro la Trie
  dfs1(st,0,1);// 1 pq el nul forma part de mxs
  cout<<ans.size()<<endl;
  For(i,ans.size(),0) cout<<ans[i]<<endl;
}

Compilation message (stderr)

printer.cpp: In function 'void add(Node*, std::string&, int)':
printer.cpp:34:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if(i == x.size()){
      |      ~~^~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:23:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define For(i, n, x) for (int i = x; i < n; i++)
......
   88 |   For(i,ans.size(),0) cout<<ans[i]<<endl;
      |       ~~~~~~~~~~~~                      
printer.cpp:88:3: note: in expansion of macro 'For'
   88 |   For(i,ans.size(),0) cout<<ans[i]<<endl;
      |   ^~~

• 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