Submission #74728

#	Time	Username	Problem	Language	Result	Execution time	Memory
74728		goodbaton	Type Printer (IOI08_printer)	C++14	100 / 100	159 ms	63772 KiB

printer

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cstring>

using namespace std;
typedef long long ll;

#define SIZE 25010

struct NODE{
  int child[26];
  int max;
  bool fin;

  NODE(){
    for(int i=0;i<26;i++) child[i] = -1;
    max = 0;
    fin = false;
  }
};

NODE node[SIZE*21];
int node_size = 1;

char ans[SIZE*42];
int ans_size = 0;

int add(char *s,int now=0,int depth=0){

  if(s[depth]=='\0'){
    node[now].max = max(node[now].max,depth);
    node[now].fin = true;
    return node[now].max;
  }
  
  int next_c = s[depth]-'a';
  
  if(node[now].child[next_c]==-1){
    node[now].child[next_c] = node_size;
    node_size++;
  }

  node[now].max = max(node[now].max, add(s,node[now].child[next_c],depth+1) );

  return node[now].max;
}

bool fin = false;
int counter = 0;

void solve(int now=0){

  if(node[now].fin) ans[ans_size++] = 'P';
  counter++;
  
  for(int i=0;i<26;i++){
    if(node[now].child[i]==-1) continue;

    int to = node[now].child[i];
    
    if(node[now].max != node[to].max){
      ans[ans_size++] = 'a'+i;
      solve(to);
    }
  }

  for(int i=0;i<26;i++){
    if(node[now].child[i]==-1) continue;

    int to = node[now].child[i];
    
    if(node[now].max == node[to].max){
      ans[ans_size++] = 'a'+i;
      solve(to);
    }
  }

  if(counter!=node_size) ans[ans_size++] = '-';
}

int main(){
  int n;
  char word[25];

  scanf("%d",&n);

  for(int i=0;i<n;i++){
    scanf("%s",word);
    add(word);
  }
  
  solve();

  printf("%d\n",ans_size);

  for(int i=0;i<ans_size;i++){
    printf("%c\n",ans[i]);
  }
  
  return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
printer.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",word);
     ~~~~~^~~~~~~~~~~

• 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