#128573 (C++14) No.297 カードの数式

• 問題: No.297 カードの数式
• ユーザー: not_522
• 提出日時: 2016-11-06 14:17:11
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,846 bytes
• コンパイル時間: 2,481 ms
• コンパイル使用メモリ: 202,700 KB
• 実行使用メモリ: 13,644 KB
• 最終ジャッジ日時: 2024-11-25 03:19:53
• 合計ジャッジ時間: 20,097 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 15 TLE * 8

ソースコード

#include <bits/stdc++.h>

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

template<typename T, typename U> bool chmin(T& a, U b) {return a > b ? a = b, true : false;}

template<typename T, typename U> bool chmax(T& a, U b) {return a < b ? a = b, true : false;}

template<typename T> inline istream& operator>>(istream &s, vector<T> &v) {
  for (T &t : v) s >> t;
  return s;
}

template<typename T> inline ostream& operator<<(ostream &s, const vector<T> &v) {
  for (const T &t : v) s << t << endl;
  return s;
}

template<typename T> inline T min(vector<T>& v) {return *min_element(v.begin(), v.end());}

template<typename T> inline T max(vector<T>& v) {return *max_element(v.begin(), v.end());}

template<typename T> inline void sort(vector<T>& v) {sort(v.begin(), v.end());}

template<typename T, typename Function> inline void sort(vector<T>& v, Function func) {sort(v.begin(), v.end(), func);}

template<typename T> inline void rsort(vector<T>& v) {sort(v.rbegin(), v.rend());}

template<typename T> inline void reverse(vector<T>& v) {reverse(v.begin(), v.end());}

template<typename T> inline void unique(vector<T>& v) {v.erase(unique(v.begin(), v.end()), v.end());}

template<typename T> inline void nth_element(vector<T>& v, int n) {nth_element(v.begin(), v.begin() + n, v.end());}

template<typename T> inline bool next_permutation(vector<T>& v) {return next_permutation(v.begin(), v.end());}

template<typename T> inline int find(vector<T>& v, T t) {return find(v.begin(), v.end(), t) - v.begin();}

template<typename T> inline int in(vector<T> v, T t) {return find(v, t) != (int)v.size();}

template<typename T> inline int lower_bound(vector<T>& v, T t) {return lower_bound(v.begin(), v.end(), t) - v.begin();}

template<typename T> inline int upper_bound(vector<T>& v, T t) {return upper_bound(v.begin(), v.end(), t) - v.begin();}

template<typename T> inline T accumulate(const vector<T>& v, function<T(T, T)> func = plus<T>()) {return accumulate(v.begin(), v.end(), T(), func);}

template<typename T> inline void adjacent_difference(vector<T>& v) {adjacent_difference(v.begin(), v.end(), v.begin());}

template<typename T> inline void adjacent_difference(vector<T>& v, vector<T>& u) {adjacent_difference(v.begin(), v.end(), u.begin());}

template<typename T> inline void partial_sum(vector<T>& v, vector<T>& u) {partial_sum(v.begin(), v.end(), u.begin());}

template<typename T> inline T inner_product(vector<T>& v, vector<T>& u) {return inner_product(v.begin(), v.end(), u.begin(), T(0));}

template<typename T> inline int count(const vector<T>& v, T t) {return count(v.begin(), v.end(), t);}

template<typename T, typename Function> inline int count_if(const vector<T>& v, Function func) {return count_if(v.begin(), v.end(), func);}

template<typename T, typename Function> inline void remove_if(vector<T>& v, Function func) {v.erase(remove_if(v.begin(), v.end(), func), v.end());}

template<typename T, typename Function> inline bool any_of(vector<T> v, Function func) {return any_of(v.begin(), v.end(), func);}

template<typename T> inline vector<T> subvector(vector<T>& v, int a, int b) {return vector<T>(v.begin() + a, v.begin() + b);}

template<typename T> inline int kinds(const vector<T>& v) {return set<T>(v.begin(), v.end()).size();}

template<typename T = long long> inline T toInteger(const string&);

template<> inline int toInteger<int>(const string& s) {
  return stoi(s);
}

template<> inline long toInteger<long>(const string& s) {
  return stol(s);
}

template<> inline long long toInteger<long long>(const string& s) {
  return stoll(s);
}

template<typename T = long long> inline T toInteger(const string& s, int n) {
  T res = 0;
  for (char c : s) {
    if (isdigit(c)) res = res * n + c - '0';
    else if (isalpha(c)) res = res * n + tolower(c) - 'a' + 10;
  }
  return s[0] == '-' ? -res : res;
}

template<typename T> struct Digit {
  T operator() (string& s, int& p) {
    if (!isdigit(s[p])) throw "empty term";
    if (s[p] == '0' && p + 1 < (int)s.size() && !isdigit(s[p + 1])) throw "leading zeros";
    string res;
    for (; isdigit(s[p]); ++p) res += s[p];
    return toInteger<T>(res);
  }
};

template<typename T> struct LeadingZeros {
  T operator() (string& s, int& p) {
    if (!isdigit(s[p])) throw "empty term";
    string res;
    for (; isdigit(s[p]); ++p) res += s[p];
    return toInteger<T>(res);
  }
};

template<typename T = long long, typename Lexer = Digit<T>> class Parser {
private:
  string s;
  int p;
  unordered_map<char, function<T(T)>> unary_operator;
  vector<unordered_map<char, function<T(T, T)>>> binary_operator;
  unordered_map<char, char> brackets;

  T term() {
    if (brackets.count(s[p])) {
      const char end = brackets[s[p]];
      ++p;
      T res = expr(0);
      if (s[p] != end) throw "mismatch brackets";
      ++p;
      return res;
    }
    if (unary_operator.count(s[p])) {
      auto f = unary_operator[s[p]];
      ++p;
      return f(term());
    }
    Lexer lexer;
    return lexer(s, p);
  }

  T expr(size_t level) {
    if (level == binary_operator.size()) return term();
    T res = expr(level + 1);
    for (char c; c = s[p++], binary_operator[level].count(c);) res = binary_operator[level][c](res, expr(level + 1));
    --p;
    return res;
  }

public:
  void addUnaryOperator(function<T(T)> func, char c) {
    unary_operator[c] = func;
  }

  void addBinaryOperator(function<T(T, T)> func, char c, size_t level) {
    if (binary_operator.size() <= level) binary_operator.resize(level + 1);
    binary_operator[level][c] = func;
  }

  void addBrackets(char begin, char end) {
    brackets[begin] = end;
  }

  long long parse(const string& s) {
    this->s = s;
    p = 0;
    return expr(0);
  }
};

template<typename T = long long> inline T parse(const string& s) {
  Parser<T> parser;
  parser.addUnaryOperator([](T t){return +t;}, '+');
  parser.addUnaryOperator(negate<T>(), '-');
  parser.addBinaryOperator(plus<T>(), '+', 0);
  parser.addBinaryOperator(minus<T>(), '-', 0);
  parser.addBinaryOperator(multiplies<T>(), '*', 1);
  parser.addBinaryOperator(divides<T>(), '/', 1);
  parser.addBrackets('(', ')');
  return parser.parse(s);
}

int main() {
  int n;
  cin >> n;
  vector<string> c(n);
  cin >> c;
  sort(c);
  int64_t mx = numeric_limits<int64_t>::min();
  int64_t mn = numeric_limits<int64_t>::max();
  do {
    string s = accumulate(c);
    Parser<int64_t, LeadingZeros<int64_t>> parser;
    parser.addBinaryOperator(plus<int64_t>(), '+', 0);
    parser.addBinaryOperator(minus<int64_t>(), '-', 0);
    try {
      int64_t res = parser.parse(s);
      chmax(mx, res);
      chmin(mn, res);
    } catch (const char* error) {
    }
  } while (next_permutation(c));
  cout << mx << " " << mn << endl;
}