oj.uz

답안 #808982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
808982 2023-08-05T13:17:08 Z Boomyday Type Printer (IOI08_printer) C++17
80 / 100
 466 ms 262144 KB 
//
// Created by adavy on 8/5/2023.
//
//
// Created by adavy on 2/4/2023.
//
//
// Created by adavy on 1/31/2023.
//
// My Header
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second



#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!

vector<char> toPrint;

struct Trie{
    bool active = 0;
    vector<Trie> links;
    int numWords=0;
    int wordsTot=0;
    bool special = 0;

    void activate(){
        active = 1;
        numWords = 0;
        wordsTot = 0;
        special = 0;
        links.rsz(26);
    }

    void dfs(){
        F0R(i, numWords) toPrint.pb('P');
        int specialFound = -1;
        F0R(i, 26){
            if (links[i].active&&links[i].wordsTot>0){
                if (links[i].special){
                    specialFound =i;
                    continue;
                }
                toPrint.pb('a'+i);
                links[i].dfs();
                toPrint.pb('-');
            }
        }
        if (specialFound!=-1){
            toPrint.pb('a'+specialFound);
            links[specialFound].dfs();
            toPrint.pb('-');
        }

    }

    void add_word(string& s, bool isSpecial = 0){
        special = isSpecial;
        wordsTot++;
        if (s.size()==0){ numWords++; return;}
        int nextChar = s.back()-'a';

        if (links[nextChar].active == 0) links[nextChar].activate();

        s.pop_back();
        links[nextChar].add_word(s,isSpecial);
    }
};


int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    vector<str> words(n);





    Trie t;
    t.activate();
    trav(i, words){ cin >> i; reverse(all(i));}
    std::sort(all(words), []
            (const std::string& first, const std::string& second){
        return first.size() < second.size();
    });
    int bs = words.back().size();
    F0R(i, words.size()-1) t.add_word(words[i]);
    t.add_word(words.back(),1);
    t.dfs();

    cout << toPrint.size()-bs << endl;
    //trav(i, toPrint) cout << i << endl;
    F0R(i, toPrint.size()-bs) cout << toPrint[i] << endl;

}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:47:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
printer.cpp:48:18: note: in expansion of macro 'FOR'
   48 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
printer.cpp:143:5: note: in expansion of macro 'F0R'
  143 |     F0R(i, words.size()-1) t.add_word(words[i]);
      |     ^~~
printer.cpp:47:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
printer.cpp:48:18: note: in expansion of macro 'FOR'
   48 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
printer.cpp:149:5: note: in expansion of macro 'F0R'
  149 |     F0R(i, toPrint.size()-bs) cout << toPrint[i] << endl;
      |     ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 8796 KB Output is correct
2 Correct 23 ms 11008 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 31292 KB Output is correct
2 Correct 154 ms 67264 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 79348 KB Output is correct
2 Correct 50 ms 16716 KB Output is correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 466 ms 199796 KB Output is correct
2 Runtime error 104 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 155676 KB Output is correct
2 Runtime error 96 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -