Submission #66380

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
66380	2018-08-10T10:51:15 Z	forestryks	Savez (COCI15_savez)	C++14	Compilation error	0 ms	0 KB

savez

///////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

// #define int long long

#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout)
#define f first
#define s second
#define x1 x1qwer
#define y1 y1qwer
#define right right123
#define left left123
#define foreach(it, v) for (auto it : v)
#define rep(it, n) for (int it = 0; it < n; ++it)
#define forin(it, l, r) for (int it = l; it < r; ++it)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double DINF = numeric_limits<double>::infinity();
const ll MOD = 1e9 + 7;
const double EPS = 1e-7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
mt19937 mmtw_(MOD);
uniform_int_distribution<ll> rd_;
ll randomll() { return rd_(mmtw_);}
ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; }
template <class T> T fact(T n) { if (n == 1) return 1; return n * fact(n - 1); }
////////////////////////////////////////////////////////////////////////////////////////////////

struct MyMap : vector<pair<char, int>> {
    int& operator[](const int v) {
        auto it = lower_bound(this->begin(), this->end(), make_pair(v, -1));
        if (it != this->end() && it->first == v) {
            return it->second;
        }
        return this->insert(it, {v, 0})->second;
    }
};

const int MAXN = 1e6 + 5;

int n;
int last = 1;
// map<int, int> to[MAXN];
MyMap to[MAXN];
int p[MAXN];
vector<string> s;
int term[MAXN];
int res[MAXN];

int get(const string &s, int i) {
    return (s[i] - 'A') + (s[s.size() - 1 - i] - 'A') * 32;
}

int trie_add(const string &s) {
    int n = s.size();
    int v = 0;
    for (int i = 0; i < n; ++i) {
        int ch = get(s, i);

        if (to[v][ch] == 0) {
            to[v][ch] = last;
            p[last] = v;

            v = last++;
        } else {
            v = to[v][ch];
        }
    }

    res[v]++;
    term[v]++;

    int r = res[v];

    while (p[v] != -1) {
        res[p[v]] = max(res[p[v]], res[v]);
        v = p[v];
    }

    return r;
}

int main() {
    FAST_IO;
    cin >> n;
    rep(i, n) {
        string a;
        cin >> a;
        s.push_back(a);
    }

    reverse(s.begin(), s.end());

    p[0] = -1;
    int res = 0;
    for (int i = 0; i < n; ++i) {;
        res = max(res, trie_add(s[i]));
    }

    cout << res << endl;
}

Compilation message

In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<char, int>*, std::vector<std::pair<char, int> > >; _Value = const std::pair<int, int>]':
/usr/include/c++/7/bits/stl_algobase.h:959:14:   required from '_ForwardIterator std::__lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<char, int>*, std::vector<std::pair<char, int> > >; _Tp = std::pair<int, int>; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
/usr/include/c++/7/bits/stl_algobase.h:993:32:   required from '_ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<char, int>*, std::vector<std::pair<char, int> > >; _Tp = std::pair<int, int>]'
savez.cpp:38:75:   required from here
/usr/include/c++/7/bits/predefined_ops.h:65:22: error: no match for 'operator<' (operand types are 'std::pair<char, int>' and 'const std::pair<int, int>')
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: candidate: template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)
     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:888:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'std::pair<char, int>' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: candidate: template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)
     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:895:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'std::pair<char, int>' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from savez.cpp:2:
/usr/include/c++/7/bits/regex.h:1429:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)
     operator<(const sub_match<_Bi_iter>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1429:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'std::pair<char, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from savez.cpp:2:
/usr/include/c++/7/bits/regex.h:1349:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)
     operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1349:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'const std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from savez.cpp:2:
/usr/include/c++/7/bits/regex.h:1272:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)
     operator<(const sub_match<_Bi_iter>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1272:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'std::pair<char, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from savez.cpp:2:
/usr/include/c++/7/bits/regex.h:1198:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)
     operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1198:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'const std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from savez.cpp:2:
/usr/include/c++/7/bits/regex.h:1121:5: note: candidate: template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)
     operator<(const sub_match<_Bi_iter>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1121:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'std::pair<char, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from savez.cpp:2:
/usr/include/c++/7/bits/regex.h:1041:5: note: candidate: template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)
     operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1041:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'std::pair<char, int>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from savez.cpp:2:
/usr/include/c++/7/bits/regex.h:962:5: note: candidate: template<class _BiIter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)
     operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:962:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'std::pair<char, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/c++/7/future:39:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:105,
                 from savez.cpp:2:
/usr/include/c++/7/thread:281:3: note: candidate: bool std::operator<(std::thread::id, std::thread::id)
   operator<(thread::id __x, thread::id __y) noexcept
   ^~~~~~~~
/usr/include/c++/7/thread:281:3: note:   no known conversion for argument 1 from 'std::pair<char, int>' to 'std::thread::id'
In file included from /usr/include/c++/7/forward_list:38:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:104,
                 from savez.cpp:2:
/usr/include/c++/7/bits/forward_list.h:1391:5: note: candidate: template<class _Tp, class _Alloc> bool std::operator<(const std::forward_list<_Tp, _Alloc>&, const std::forward_list<_Tp, _Alloc>&)
     operator<(const forward_list<_Tp, _Alloc>& __lx,
     ^~~~~~~~
/usr/include/c++/7/bits/forward_list.h:1391:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'std::pair<char, int>' is not derived from 'const std::forward_list<_Tp, _Alloc>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from savez.cpp:2:
/usr/include/c++/7/valarray:1186:1: note: candidate: template<class _Tp> std::_Expr<std::_BinClos<std::__less, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__less, _Tp>::result_type> std::operator<(const _Tp&, const std::valarray<_Tp>&)
 _DEFINE_BINARY_OPERATOR(<, __less)
 ^
/usr/include/c++/7/valarray:1186:1: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'const std::pair<int, int>' is not derived from 'const std::valarray<_Tp>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from savez.cpp:2:
/usr/include/c++/7/valarray:1186:1: note: candidate: template<class _Tp> std::_Expr<std::_BinClos<std::__less, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__less, _Tp>::result_type> std::operator<(const std::valarray<_Tp>&, const _Tp&)
 _DEFINE_BINARY_OPERATOR(<, __less)
 ^
/usr/include/c++/7/valarray:1186:1: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'std::pair<char, int>' is not derived from 'const std::valarray<_Tp>'
       { return *__it < __val; }
                ~~~~~~^~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from savez.cpp:2:
/usr/include/c++/7/valarray:1186:1: note: candidate: template<class _Tp> std::_Expr<std::_BinClos<std::__less, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__less, _Tp>::result_type> std::operator<(const std::valarray<_Tp>&, const std::valarray<_Tp>&)
 _DEFINE_BINARY_OPERATOR(<, __less)
 ^
/usr/include/c++/7/valarray:1186:1: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from savez.cpp:2:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note:   'std::pair<cha