Skip to main content
mentioned bad scanf
Source Link
Edward
  • 66.6k
  • 4
  • 118
  • 282

The code currently contains equivalent to these lines (after undoing macros and use operator>> instead of horrible scanf):

The code currently contains these lines:

The code currently contains equivalent to these lines (after undoing macros and use operator>> instead of horrible scanf):

Source Link
Edward
  • 66.6k
  • 4
  • 118
  • 282

Here are some things to improve your code. First, we'll address the performance issue, followed by a number of other things that could be improved.

Use const references where practical

The code currently declares its main search function like so:

bool isin(long s, unordered_map<long,long> m)

This has two problems. First it passes by value, so a new std::unordered_map is created on every call. This is extremely wasteful of both time and memory. Second, it should actually be a const reference.

bool isin(long s, const unordered_map<long,long> &m)

Results of that single change on the sample data provided in the question:

$$ \begin{array}{|l|r|} \hline \text{program} & \text{time (ms)} \\ \hline \text{Python 2.7} & 15 \\ \text{original C++} & 2475 \\ \text{C++ with const ref} & 3 \\ \hline \end{array} $$

As you can see, despite the title of this question, in fact the C++ version is about 5 times faster than the Python version, with no other changes applied.

Don't abuse using namespace std

Putting using namespace std within your program is generally a bad habit that you'd do well to avoid.

Avoid C-style macros

I'd advise not using C-style macros like REP, Fi, etc. They only make your program harder to read and understand and obfuscate the underlying meaning. Further, function-like macros are notorious sources of bugs in C. They have very little use in modern C++.

Eliminate unused typedef

The LL typedef is never used in the program and could simply be omitted.

Use whitespace to improve readability

Lines like this:

long ps2=deuxpownmodprime(n/2,mod);

become easier to read with a little bit of whitespace:

long ps2 = deuxpownmodprime(n/2, mod);

Eliminate magic numbers

The constants 71 is used in multiple places. It would be better to have such numbers as named const or constexpr values so that it would be clear what those numbers represent.

Eliminate unused variables

Unused variables are a sign of poor code quality, so eliminating them should be a priority. In this code, nbm is defined but unused. Your compiler is probably also smart enough to tell you that, if you ask it to do so.

Use consistent formatting

The code as posted has inconsistent use of {} which makes it a little harder to read and understand. Pick a style and apply it consistently.

Iterate over const references where possible

In the main() routine, the range for loops should iterate over const references instead of forcing temporary copies. In other words, change the code from this:

for (auto it : ot) {

to this:

for (const auto &it : ot) {

Simplify the code using uniform initialization syntax

The code currently has a number of lines like this:

ta.insert(pair<long, long>(m, it.second));

This can easily be simplified using uniform initialization syntax.

ta.insert({m, it.second});

Also these two lines:

std::unordered_map<long, long> ot;
ot.insert(pair<long, long>(0, 1));

Can be simplified to this:

std::unordered_map<long, long> ot{{0,1}};

Use constexpr where practical

In main, the variables decomps and mod are actually used as constants, so it would make sense to at least declare them as const and preferably constexpr.

Understand the risk of unsanitized user input

The code currently contains these lines:

int dn[71] = { 0 };
for (int i = 0; i < n; ++i) {
    int a;
    std::cin >> a;
    dn[a]++;
}

What happens if one of the input numbers is greater than 71? Undefined behavior and probably a program crash. The problem constrains no doubt tell you that all of the data is guaranteed good, but adding in a bounds check here would make the program more robust and cost very, very little time. One way to do it would be to use std::array:

std::array<int, 71> dn{};  // value-initialized to all zero
for (int i = 0; i < n; ++i) {
    int a;
    std::cin >> a;
    dn.at(a)++;
}

Use C++ idioms

With the modification suggested above, some of the code looks like this:

for (const auto &it : ta) {
    if (!isin(it.first, ot)) {
        ot[it.first] = it.second;
    } else {
        ot[it.first] += it.second;
    }
}

The isin function is not bad, but to experienced C++ programmers, this might be clearer:

for (const auto &it : ta) {
    if (ot.find(it.first) == ot.end()) {
        ot[it.first] = it.second;
    } else {
        ot[it.first] += it.second;
    }
}

However, a real C++ programmer would instead write this:

for (const auto &it : ta) {
    ot[it.first] += it.second;
}

This works because operator[] will create the entry if it does not exist (value initializing the data value to 0) and then adds the desired value. The previous loop can similarly be written like this:

for (const auto &it : ot) {
    ta[(it.first) ^ decomps[i]] += it.second;
}

Add some comments

This looks like a clever algorithm, but it's not obvious how it works or why. Comments describing, for instance, what the values of decomps mean and how they're derived, would add a lot to the program.