第二回 オフラインリアルタイムどう書く その1

今回もQiita上でだけでの参加。

問題：

• http://nabetani.sakura.ne.jp/hena/ord2/

時間を測ってみたところ、問題を読み始めてから結果が出るまでおよそ40分ぐらいでした。

#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>

typedef std::vector<unsigned int> Field;

struct Data
{
    const char* input;
    const char* output;
};

const Data data[] =
{
    /* 0*/ { "ff-2f-23-f3-77-7f-3b", "1f-03-00-1c-0d-0f-06" },
    /* 1*/ { "01", "00" },
    /* 2*/ { "00", "00" },
    /* 3*/ { "7a-4e", "0c-02" },
    /* 4*/ { "56-b6", "08-14" },
    /* 5*/ { "12-12-12", "00-00-00" },
    /* 6*/ { "de-ff-7b", "0a-0f-05" },
    /* 7*/ { "95-be-d0", "05-1e-20" },
    /* 8*/ { "7c-b0-bb", "1c-20-2b" },
    /* 9*/ { "7a-b6-31-6a", "3a-56-11-2a" },
    /*10*/ { "32-0e-23-82", "18-06-11-40" },
    /*11*/ { "ff-7f-bf-df-ef", "0f-07-0b-0d-0e" },
    /*12*/ { "75-df-dc-6e-42", "35-5f-5c-2e-02" },
    /*13*/ { "62-51-ef-c7-f8", "22-11-6f-47-78" },
    /*14*/ { "0c-47-8e-dd-5d-17", "04-23-46-6d-2d-0b" },
    /*15*/ { "aa-58-5b-6d-9f-1f", "52-28-2b-35-4f-0f" },
    /*16*/ { "ff-55-d5-75-5d-57", "0f-00-08-04-02-01" },
    /*17*/ { "fe-fd-fb-f7-ef-df-bf", "7e-7d-7b-77-6f-5f-3f" },
    /*18*/ { "fd-fb-f7-ef-df-bf-7f", "7e-7d-7b-77-6f-5f-3f" },
    /*19*/ { "d9-15-b5-d7-1b-9f-de", "69-05-55-67-0b-4f-6e" },
    /*20*/ { "38-15-fd-50-10-96-ba", "18-05-7d-20-00-46-5a" },
    /*21*/ { "fe-fd-fb-f7-ef-df-bf-7f", "fe-fd-fb-f7-ef-df-bf-7f" },
           { 0, 0 }
};

std::istream& operator >> (std::istream& in, Field& field)
{
    in >> std::hex;
    unsigned int n;
    do
    {
        in >> n;
        field.push_back(n);
        char c;
        in >> c;
    } while(in.good());
    return in;
}

std::ostream& operator << (std::ostream& out, const Field& field)
{
    int fill = out.fill('0');
    out << std::hex;
    Field::const_iterator i = field.begin();
    out << std::setw(2) << *i++;
    for(; i != field.end(); ++i)
    {
        out << "-" << std::setw(2) << *i;
    }
    out << std::dec;
    out.fill(fill);
    return out;
}

int main(int, char* [])
{
    for(const Data* d = data; d->input != 0; ++d)
    {
        Field field;
        std::istringstream iss(d->input);
        iss >> field;

        Field::iterator i = field.begin();
        Field::value_type v = *i++;
        for(; i != field.end(); ++i)
        {
            v &= *i;
        }

        for(int i = 7; i >= 0; --i)
        {
            if(((v >> i) & 1) != 0)
            {
                for(Field::iterator f = field.begin(); f != field.end(); ++f)
                {
                    *f = (*f & (0xffu >> (8 - i))) | ((*f >> 1) & (0xffu << i));
                }
            }
        }

        std::ostringstream oss;
        oss << field;
        std::string result = oss.str();
        std::cout << result << " : " << ((result == d->output) ? "PASSED" : "FAILED") << std::endl;
    }

    return 0;
}