oj.uz

Submission #1094967

# Submission time Handle Problem Language Result Execution time Memory
1094967 2024-10-01T04:10:41 Z SoMotThanhXuan Type Printer (IOI08_printer) C++17
100 / 100
 105 ms 103944 KB 
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define iii pair<int,ii>
#define vii vector<ii>
#define viii vector<iii>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
void minimize(int &u,int v){
    if(v<u)u=v;
}
void maximize(int &u,int v){
    if(v>u)u=v;
}
void minimizell(long long &u,long long v){
    if(v<u)u=v;
}
void maximizell(long long &u,long long v){
    if(v>u)u=v;
}
const int N=1e5+2;
const int mod=1e9+7;
const int inf=1e9+8;
const long long infll=1e18+8;
const int LOG=19;
const int inverse_mod=1e9+5;
string a[N];
string res="";
struct trieNode{
    trieNode *child[26];
    int cnt;
    trieNode(){
        cnt=0;
        for(int i=0;i<=25;++i){
            child[i]=nullptr;
        }
    }
};
trieNode *root;
void addString(const string &s){
    trieNode *p=root;
    int n=s.size();
    for(int i=0;i<n;++i){
        int f=s[i]-'a';
        if(p->child[f]==nullptr){
            p->child[f]=new trieNode();
        }
        p=p->child[f];
    }
    p->cnt++;
}
string t="";
void dfs(trieNode *p){
    for(int i=1;i<=p->cnt;++i)res+='P';
    for(int i=0;i<=25;++i){
        if(p->child[i]!=nullptr){
            res+=char(i+'a');
            dfs(p->child[i]);
            res+='-';
        }
    }

}
void init(){
    root =new trieNode();
    int n;
    cin >> n;
    int pos=0;
    int maxsize=0;
    for(int i=1;i<=n;++i){
        cin >> a[i];
        if(a[i].size()>maxsize){
            maxsize=a[i].size();
            pos=i;
        }
    }
    t=a[pos];
    for(int i=1;i<=n;++i){
        if(a[i][0]!=t[0]){
            addString(a[i]);
        }
    }
    dfs(root);
    for(int i=1;i<=n;++i){
        if(a[i][0]==t[0]){
            addString(a[i]);
        }
    }
    trieNode *p=root;
    for(int i=0;i<t.size()-1;++i){
        p=p->child[t[i]-'a'];
        res+=t[i];
        for(int i=1;i<=p->cnt;++i){
            res+='P';
        }
        for(int j=0;j<=25;++j){
            if(char(j+'a')!=t[i+1] and p->child[j]!=nullptr){
                res.push_back(char(j+'a'));
                dfs(p->child[j]);
                res.push_back('-');
            }
        }

    }
    res+=t[maxsize-1];
    p=p->child[t[maxsize-1]-'a'];
    for(int i=1;i<=p->cnt;++i){
        res+='P';
    }
    cout << res.size() << '\n';
    for(int i=0;i<(int)res.size();++i){
        cout << res[i] << "\n";
    }
}

int main(){
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    return 0;
}

Compilation message

printer.cpp: In function 'void init()':
printer.cpp:72:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |         if(a[i].size()>maxsize){
      |            ~~~~~~~~~~~^~~~~~~~
printer.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0;i<t.size()-1;++i){
      |                 ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 2 ms 3588 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3672 KB Output is correct
2 Correct 3 ms 4188 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 5464 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9052 KB Output is correct
2 Correct 13 ms 15612 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17648 KB Output is correct
2 Correct 6 ms 6748 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 39668 KB Output is correct
2 Correct 77 ms 87820 KB Output is correct
3 Correct 46 ms 47216 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 31724 KB Output is correct
2 Correct 105 ms 103944 KB Output is correct
3 Correct 55 ms 53156 KB Output is correct
4 Correct 84 ms 98296 KB Output is correct