oj.uz

답안 #321258

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321258 2020-11-11T18:25:23 Z vukasinbabic06 Type Printer (IOI08_printer) C++14
10 / 100
 53 ms 19100 KB 
#include<bits/stdc++.h>
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define NL(x) " \n"[(x)]
#define lld long long
#define pil pair<int,lld>
#define pli pair<lld,int>
#define pll pair<lld,lld>
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXC 1000000
int trie[MAXC][26], idxx, poslednji, slovo[MAXC];
bool kraj[MAXC], najduza[MAXC];
stack<char> stek;
string w, resenje="";
void add(string &x) {
    int node = 0;
    for(int t = 0; t < x.size(); t++) {
        int c = x[t]-'a';
        if(trie[node][c] == 0) trie[node][c] = ++idxx;
        node = trie[node][c];
        slovo[node]=c;
    }
    kraj[node] = true;
}
void query() {
    int node = 0;
    for(int t = 0; t < w.size(); t++) {
        int c = w[t]-'a';
        node = trie[node][c];
        najduza[node]=true;
    }
}
void dfs(int x){
    int posl=-1;
    for(int i=0; i<26; i++){
        int c=trie[x][i];
        while(stek.size() and (stek.top()!=slovo[x])){
            stek.pop();
            resenje+="-\n";
        }
        if(!najduza[c]){
            if(c!=0){
                resenje+=char(i+'a');
                resenje+="\n";
                stek.push(i);
                if(kraj[c]){
                    resenje+="P\n";
                }
                dfs(c);
            }
        }
        else posl=i;
    }
    //cout<<posl;
    if(posl!=-1){
        int c=trie[x][posl];
        if(c!=0){
            resenje+=char(posl+'a');
            resenje+="\n";
            stek.push(posl);
            if(kraj[c]){
                resenje+="P\n";
            }
            dfs(trie[x][posl]);
        }
    }
    //int c=trie[x][posl];
    /*if(c!=0){
        resenje+=char(posl+'a');
        resenje+="\n";
        dfs(trie[x][posl]);
    }*/
}
int f(string a) {
    int r=0;
    int n1 = a.size(), n2 = w.size();
    for (int i=0, j=0; (i<=(n1-1))&&(j<=(n2-1)); i++,j++) {
        if (a[i] != w[j])
            break;
        r++;
    }
    return r;
}
int main() {
    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0);
   // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0);
    int N, l=0; cin >> N;
    for(int i = 1; i <= N; i++) {
        string x; cin >> x;
        if(x.size()>l){
            l=x.size();
            w=x;
        }
        add(x);
    }
    query();
    //cout<<"meda"<<endl;
    dfs(0);
    cout<<resenje.size()/2<<endl<<resenje;
   /* for(int i=0; i<n; i++){
        a[i].fi=f(a[i].se);
    }
    sort(all(a));
    for(auto x : a) cout<<x.fi<<x.se;*/
}

Compilation message

printer.cpp: In function 'void add(std::string&)':
printer.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int t = 0; t < x.size(); t++) {
      |                    ~~^~~~~~~~~~
printer.cpp: In function 'void query()':
printer.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int t = 0; t < w.size(); t++) {
      |                    ~~^~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:100:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |         if(x.size()>l){
      |            ~~~~~~~~^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB printed invalid word

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1132 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 3364 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 7948 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 19100 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 45 ms 15008 KB printed invalid word
2 Halted 0 ms 0 KB -