#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse") // Enable global common subexpression elimination
#pragma GCC optimize("-fgcse-lm") // Perform load motion during GIMPLE optimization
#pragma GCC optimize("-fipa-sra") // Enable interprocedural scalar replacement of aggregates
#pragma GCC optimize("-ftree-pre") // Enable partial redundancy elimination
#pragma GCC optimize("-ftree-vrp") // Perform value range propagation
#pragma GCC optimize("-fpeephole2") // Enable peephole optimizations after register allocation
#pragma GCC optimize("-ffast-math") // Enable fast math optimizations (less strict IEEE compliance)
#pragma GCC optimize("-fsched-spec") // Allow speculative motion of instructions
#pragma GCC optimize("unroll-loops") // Enable loop unrolling
#pragma GCC optimize("-falign-jumps") // Align branch targets to improve performance
#pragma GCC optimize("-falign-loops") // Align loop entry points
#pragma GCC optimize("-falign-labels") // Align branch labels
#pragma GCC optimize("-fdevirtualize") // Enable devirtualization optimizations
#pragma GCC optimize("-fcaller-saves") // Save caller-saved registers around function calls
#pragma GCC optimize("-fcrossjumping") // Merge identical code sequences at jumps
#pragma GCC optimize("-fthread-jumps") // Perform thread jump optimizations
#pragma GCC optimize("-funroll-loops") // Perform aggressive loop unrolling
#pragma GCC optimize("-fwhole-program") // Perform whole-program optimizations
#pragma GCC optimize("-freorder-blocks") // Reorder basic blocks to improve branch prediction
#pragma GCC optimize("-fschedule-insns") // Reschedule instructions to reduce pipeline stalls
#pragma GCC optimize("inline-functions") // Inline functions aggressively
#pragma GCC optimize("-ftree-tail-merge") // Merge identical code at the ends of functions
#pragma GCC optimize("-fschedule-insns2") // Further reschedule instructions after register allocation
#pragma GCC optimize("-fstrict-aliasing") // Enforce strict aliasing rules
#pragma GCC optimize("-fstrict-overflow") // Assume signed arithmetic overflow does not occur
#pragma GCC optimize("-falign-functions") // Align function entry points
#pragma GCC optimize("-fcse-skip-blocks") // Perform CSE (common subexpression elimination) across blocks
#pragma GCC optimize("-fcse-follow-jumps") // Perform CSE following jumps
#pragma GCC optimize("-fsched-interblock") // Perform instruction scheduling across basic blocks
#pragma GCC optimize("-fpartial-inlining") // Allow partial inlining of functions
#pragma GCC optimize("no-stack-protector") // Disable stack protection mechanisms
#pragma GCC optimize("-freorder-functions") // Reorder function layout to improve performance
#pragma GCC optimize("-findirect-inlining") // Perform indirect inlining
#pragma GCC optimize("-fhoist-adjacent-loads") // Hoist adjacent loads
#pragma GCC optimize("-frerun-cse-after-loop") // Re-run common subexpression elimination after loop optimizations
#pragma GCC optimize("inline-small-functions") // Inline very small functions
#pragma GCC optimize("-finline-small-functions") // Inline small functions more aggressively
#pragma GCC optimize("-ftree-switch-conversion") // Optimize switch statements into conditional chains
#pragma GCC optimize("-foptimize-sibling-calls") // Optimize sibling and tail recursive calls
#pragma GCC optimize("-fexpensive-optimizations") // Perform more expensive optimizations
#pragma GCC optimize("-funsafe-loop-optimizations") // Assume loops do not overflow
#pragma GCC optimize("inline-functions-called-once") // Inline functions called only once
#pragma GCC optimize("-fdelete-null-pointer-checks") // Remove redundant null pointer checks

#include <algorithm>  // for std::transform
#include <chrono>     // for performance measurement
#include <cstring>    // for std::strcpy
#include <iomanip>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

// Define pointers to functions for string conversion
using ptr = string (*)(string);
using ptr_cr = string (*)(const string&);

// Struct to store function pointers and their names
struct func_info {
    ptr func;          // Function pointer
    string name;       // Name of the function
};

struct func_info_cr {
    ptr_cr func;       // Function pointer (const reference version)
    string name;       // Name of the function
};

vector<pair<string, int64_t>> results; // Stores function performance results
map<string, int> winner; // Tracks the number of wins for each function

string strlwr_a_cr(const string& input) {
    string result = input;
    for (size_t i = 0; i < result.size(); ++i) {
        if (result[i] >= 'A' && result[i] <= 'Z') {
            result[i] += 32;
        }
    }
    return result;
}

string strlwr_a(string input) {
    for (size_t i = 0; i < input.size(); ++i) {
        if (input[i] >= 'A' && input[i] <= 'Z') {
            input[i] += 32;
        }
    }
    return input;
}

string strlwr_a_bitwise_operation_cr(const string& input) {
    string result = input;
    for (size_t i = 0; i < result.size(); ++i) {
        if (result[i] >= 'A' && result[i] <= 'Z') {
            result[i] |= 32;
        }
    }
    return result;
}

string strlwr_a_bitwise_operation(string input) {
    for (size_t i = 0; i < input.size(); ++i) {
        if (input[i] >= 'A' && input[i] <= 'Z') {
            input[i] |= 32;
        }
    }
    return input;
}

string strlwr_a_tolower_cr(const string& input) {
    string result = input;
    for (size_t i = 0; i < result.size(); ++i) {
        if (result[i] >= 'A' && result[i] <= 'Z') {
            result[i] = tolower(result[i]);
        }
    }
    return result;
}

string strlwr_a_tolower(string input) {
    for (size_t i = 0; i < input.size(); ++i) {
        if (input[i] >= 'A' && input[i] <= 'Z') {
            input[i] = tolower(input[i]);
        }
    }
    return input;
}

string strlwr_b_cr(const string& input) {
    string result = input;
    // Extra space for null terminator
    char cstr[result.size() + 1];
    strcpy(cstr, result.c_str());
    strlwr(cstr);
    return string(cstr);
}

string strlwr_b(string str) {
    char cstr[str.size()];
    strcpy(cstr, str.c_str());
    strlwr(cstr);
    return string(cstr);
}

string strlwr_b_plus1(string str) {
    // Extra space for null terminator
    char cstr[str.size() + 1];
    strcpy(cstr, str.c_str());
    strlwr(cstr);
    return string(cstr);
}

char cstr_array[100000001];

string strlwr_b_gobal_array_cr(const string& input) {
    string result = input;
    strcpy(cstr_array, result.c_str());
    strlwr(cstr_array);
    return string(cstr_array);
}

string strlwr_b_gobal_array(string str) {
    strcpy(cstr_array, str.c_str());
    strlwr(cstr_array);
    return string(cstr_array);
}

string strlwr_c_cr(const string& input) {
    return string(strlwr((char*)input.c_str()));
}

string strlwr_c(string str) { return string(strlwr((char*)str.c_str())); }

string strlwr_d_cr(const string& input) {
    string result = input;
    std::transform(result.begin(), result.end(), result.begin(), ::tolower);
    return result;
}

string strlwr_d(string str) {
    std::transform(str.begin(), str.end(), str.begin(), ::tolower);
    return str;
}

string strlwr_e_cr(const string& input) {
    string str = input;
    std::for_each(str.begin(), str.end(), [](char& c) { c = ::tolower(c); });
    return str;
}

string strlwr_e(string str) {
    std::for_each(str.begin(), str.end(), [](char& c) { c = ::tolower(c); });
    return str;
}

string strlwr_f_cr(const string& input) {
    stringstream ss;
    for (char c : input) {
        ss << static_cast<char>(tolower(c));
    }
    return ss.str();
}

string strlwr_f(string str) {
    stringstream ss;
    for (char c : str) {
        ss << static_cast<char>(tolower(c));
    }
    return ss.str();
}

string strlwr_g_cr(const string& input) {
    string str = input;
    for (auto it = str.begin(); it != str.end(); it++) {
        *it = tolower(*it);
    }
    return str;
}

string strlwr_g(string str) {
    for (auto it = str.begin(); it != str.end(); it++) {
        *it = tolower(*it);
    }
    return str;
}

void testfunc(ptr_cr func, const string& func_name, const string& str, int count) {
    // Measure execution time for functions that take `const string&` as input
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < count; ++i) {
        func(str); // Call the function repeatedly
    }
    auto duration = chrono::duration_cast<chrono::microseconds>(
        chrono::high_resolution_clock::now() - start);
    results.push_back({func_name, duration.count()}); // Store the results
}

void testfunc(ptr func, const string& func_name, const string& str, int count) {
    // Measure execution time for functions that take `string` as input
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < count; ++i) {
        func(str); // Call the function repeatedly
    }
    auto duration = chrono::duration_cast<chrono::microseconds>(
        chrono::high_resolution_clock::now() - start);
    results.push_back({func_name, duration.count()}); // Store the results
}

void print_results(int count) {
    // Display performance results in a sorted order
    cout << "Results:" << endl;
    sort(results.begin(), results.end(),
         [](const pair<string, int64_t>& a, const pair<string, int64_t>& b) {
             return a.second < b.second; // Sort by execution time
         });
    for (const auto& result : results) {
        cout << setw(7) << result.second << "ms" // Total time in milliseconds
             << "   avg:" << fixed << setprecision(4)
             << 1.0 * result.second / count // Average time per operation
             << "   " << result.first << endl; // Function name
    }
    auto min_time = min_element(
        results.begin(), results.end(),
        [](const pair<string, int64_t>& a, const pair<string, int64_t>& b) {
            return a.second < b.second;
        });
    winner[min_time->first]++; // Increment the winner counter for the fastest function
    cout << "The fastest function is " << min_time->first << " with time "
         << min_time->second << " ms" << endl;
}

vector<func_info> func_list = {
    // List of functions to test with `string` parameter
    func_info{strlwr_a, "strlwr_a"},
    func_info{strlwr_a_tolower, "strlwr_a_tolower"},
    func_info{strlwr_a_bitwise_operation, "strlwr_a_bitwise_operation"},
    func_info{strlwr_b, "strlwr_b"},
    func_info{strlwr_b_plus1, "strlwr_b_plus1"},
    func_info{strlwr_b_gobal_array, "strlwr_b_gobal_array"},
    func_info{strlwr_c, "strlwr_c"},
    func_info{strlwr_d, "strlwr_d"},
    func_info{strlwr_e, "strlwr_e"},
    func_info{strlwr_f, "strlwr_f"},
    func_info{strlwr_g, "strlwr_g"}};

vector<func_info_cr> func_list_cr = {
    // List of functions to test with `const string&` parameter
    func_info_cr{strlwr_a_cr, "strlwr_a_cr"},
    func_info_cr{strlwr_a_tolower_cr, "strlwr_a_tolower_cr"},
    func_info_cr{strlwr_a_bitwise_operation_cr, "strlwr_a_bitwise_operation_cr"},
    func_info_cr{strlwr_b_cr, "strlwr_b_cr"},
    func_info_cr{strlwr_b_gobal_array_cr, "strlwr_b_gobal_array_cr"},
    func_info_cr{strlwr_c_cr, "strlwr_c_cr"},
    func_info_cr{strlwr_d_cr, "strlwr_d_cr"},
    func_info_cr{strlwr_e_cr, "strlwr_e_cr"},
    func_info_cr{strlwr_f_cr, "strlwr_f_cr"},
    func_info_cr{strlwr_g_cr, "strlwr_g_cr"}};

void test_func_list(const string& str, int count) {
    // Test all functions with the provided string and repeat count
    for (const auto& func : func_list) {
        testfunc(func.func, func.name, str, count);
    }
    for (const auto& func : func_list_cr) {
        testfunc(func.func, func.name, str, count);
    }
    print_results(count); // Print the results
    results.clear(); // Clear results for the next test
    cout << endl;
}

int main() {
    // Run tests with various input strings and repeat counts
    cout << "Test with empty string" << endl;
    test_func_list("", 1000001);

    cout << "Test with single character: H" << endl;
    test_func_list("H", 1000001);

    cout << "Test with two characters: AH" << endl;
    test_func_list("AH", 1000001);

    cout << "Test with three characters: AHA" << endl;
    test_func_list("AHA", 1000001);

    cout << "Test with four characters: HELL" << endl;
    test_func_list("HELL", 1000001);

    cout << "Test with five characters: Hello" << endl;
    test_func_list("Hello", 1000001);

    cout << "Test with special characters: $%^&*" << endl;
    test_func_list("$%^&*", 1000001);

    string long_lower_str(100000, 'a'); // Generate a long string of 'a'
    string long_dash_str(100000, '-'); // Generate a long string of '-'
    cout << "Test with string: string(100000, 'a')" << endl;
    test_func_list(long_lower_str, 101);

    cout << "Test with string: string(100000, '-')" << endl;
    test_func_list(long_dash_str, 101);

    cout << "Test with mixed case: string(100000, 'a') + 'A' + string(100000, 'a')" << endl;
    test_func_list(long_lower_str + "A" + long_lower_str, 101);

    cout << "Test with mixed case: string(100000, '-') + 'A' + string(100000, '-')" << endl;
    test_func_list(long_dash_str + "A" + long_dash_str, 101);

    // Test with normal strings
    cout << "Test with normal string: Hello, World!" << endl;
    test_func_list("Hello, World!", 1000001);

    // Test with long strings
    cout << "Test with long string: string(100000, 'A')" << endl;
    string long_str(100000, 'A');
    test_func_list(long_str, 101);

    // Test with very long strings
    cout << "Test with very long string: string(1000000, 'A')" << endl;
    string very_long_str(1000000, 'A');
    test_func_list(very_long_str, 11);

    // Test with super long strings
    cout << "Test with super long string: string(10000000, 'A')" << endl;
    cout << "Not all functions will be tested due to array size limitations" << endl;
    string super_long_str(100000000, 'A');

    // Remove functions unsuitable for super long strings
    func_list.erase(remove_if(func_list.begin(), func_list.end(),
                              [](const func_info& f) {
                                  return f.name == "strlwr_b" ||
                                         f.name == "strlwr_b_plus1";
                              }),
                    func_list.end());
    func_list_cr.erase(remove_if(func_list_cr.begin(), func_list_cr.end(),
                                 [](const func_info_cr& f) {
                                     return f.name == "strlwr_b_cr";
                                 }),
                       func_list_cr.end());
    test_func_list(super_long_str, 1);

    // Print the winner count for each function
    cout << endl << "Winner:" << endl;
    for (const auto& w : winner) {
        cout << w.first << ": " << w.second << endl;
    }

    return 0;
}