3007

ちょっと訳ありで速くしてみた。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct Data {
    const char* s1;
    int l1;

    const char* s2;

    Data(const char* s1, int l1, const char* s2)
        : s1(s1), l1(l1), s2(s2) {}

    char operator [](int n) const {
        if (n < l1) return s1[n];
        else return s2[n - l1];
    }
};

int Length;

bool operator <(const Data& lhs, const Data& rhs)
{
    for (int i = 0; i < Length; i++) {
        if (lhs[i] != rhs[i]) return lhs[i] < rhs[i];
    }
    return false;
}

bool operator ==(const Data& lhs, const Data& rhs)
{
    for (int i = 0; i < Length; i++) {
        if (lhs[i] != rhs[i]) return false;
    }
    return true;
}

int main()
{
    string str, rstr;
    
    vector<Data> s;
    int t;

    cin >> t;
    while (t--) {
        char tmp[128];
        scanf("%s", tmp);
        s.clear();

        str = tmp;
        rstr = str;
        reverse(rstr.begin(), rstr.end());
        Length = str.size();

        const char* s1 = str.c_str();
        const char* r1 = rstr.c_str();

        s.push_back(Data(s1, Length, NULL));
        s.push_back(Data(r1, Length, NULL));

        for (int i = 1; i < Length; i++) {
            // back + front(same order)
            s.push_back(Data(s1 + i, Length - i, s1));
            s.push_back(Data(r1 + i, Length - i, r1));

            // front + r_back, r_back + front
            s.push_back(Data(s1, i, r1));
            s.push_back(Data(r1, i, s1));

            // r_front + back, back + r_front
            s.push_back(Data(r1 + i, Length - i, s1 + Length - i));
            s.push_back(Data(s1 + Length - i, i, r1 + i));
        }

        sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());

        cout << s.size() << endl;
    }
}

適当でサーセンｗ cinとscanf混ぜて使って良いのは小学生までだよねー。Lengthはグローバル変数だから、最適化されずに毎回読み込まれたりしてねーよなーとかの心配事や、そぎ落とせそうな贅肉はまだあるけどとりあえず94ms。1位は76ms。とりあえず使ってるアルゴリズムは違わなそうなので安心。あまりに時間がかかるから、何か変な方法使ってんのかな？とか思ってしまった。ところでメモリ使用量はどうやると減るんでしょうかうううう。

つかPKU最近タイマー変わった？ちょっと古いタイムと約16のアライメントが違う気がする。