#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

#include <algorithm>  // transform
#include <chrono>     // chrono
#include <cstring>    // strcpy
#include <iomanip>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

using ptr = string (*)(string);
using ptr_cr = string (*)(const string&);
// typedef string (*ptr)(string str);
// typedef string (*ptr_cr)(const string& str);

struct func_info {
    ptr func;
    string name;
};

struct func_info_cr {
    ptr_cr func;
    string name;
};

vector<pair<string, int64_t>> results;
map<string, int> winner;

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;
    // +1 是为了存放字符串结束符
    // 不加这个测试长字符串和空字符串会 segmentation fault
    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) {
    // +1 是为了存放字符串结束符
    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) {
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < count; ++i) {
        func(str);
    }
    auto duration = chrono::duration_cast<chrono::microseconds>(
        chrono::high_resolution_clock::now() - start);
    results.push_back({func_name, duration.count()});
}

void testfunc(ptr func, const string& func_name, const string& str, int count) {
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < count; ++i) {
        func(str);
    }
    auto duration = chrono::duration_cast<chrono::microseconds>(
        chrono::high_resolution_clock::now() - start);
    results.push_back({func_name, duration.count()});
}

void print_results(int count) {
    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;
         });
    for (const auto& result : results) {
        cout << setw(7) << result.second << "ms" << "   avg:" << fixed
             << setprecision(4) << 1.0 * result.second / count << "   "
             << result.first << endl;
    }
    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]++;
    cout << "The fastest function is " << min_time->first << " with time "
         << min_time->second << " ms" << endl;
}

vector<func_info> func_list = {
    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 = {
    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) {
    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);
    results.clear();
    cout << endl;
}

int main() {
    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 five characters: $%^&*" << endl;
    test_func_list("$%^&*", 1000001);

    string long_lower_str(100000, 'a');
    string long_dash_str(100000, '-');
    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 five characters: string(100000, 'a')+'A'+string(100000, "
            "'a')"
         << endl;
    test_func_list(long_lower_str + "A" + long_lower_str, 101);
    cout << "Test with five characters: string(100000, '-')+'A'+string(100000, "
            "'-')"
         << endl;
    test_func_list(long_dash_str + "A" + long_dash_str, 101);

    // 测试普通字符串下的表现
    cout << "Test with normal string: Hello, World!" << endl;
    test_func_list("Hello, World!", 1000001);

    // 测试长字符下的表现
    cout << "Test with long string: string(100000, 'A')" << endl;
    string long_str(100000, 'A');
    test_func_list(long_str, 101);

    // 测试超长字符下的表现
    cout << "Test with very long string: string(1000000, 'A')" << endl;
    string very_long_str(1000000, 'A');
    test_func_list(very_long_str, 11);

    // 只处理一次比超长还长的字符串
    cout << "Test with super long string: string(10000000, 'A')" << endl;
    cout << "Not all functions will be tested, because array is too long"
         << endl;
    string super_long_str(100000000, 'A');
    // func_list 中移除 strlwr_b 和 strlwr_b_plus1, func_list_cr 中移除
    // strlwr_b_cr
    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);

    // 输出函数赢得最快的次数
    cout << endl << "Winner:" << endl;
    for (const auto& w : winner) {
        cout << w.first << ": " << w.second << endl;
    }

    return 0;
}