Submission #668694

#	Time	Username	Problem	Language	Result	Execution time	Memory
668694		finn__	Data Transfer (IOI19_transfer)	C++17	0 / 100	5 ms	2996 KiB

transfer

#include "transfer.h"

std::vector<int> get_attachment(std::vector<int> source)
{
    unsigned const lgn = 32 - __builtin_clz(source.size());
    std::vector<int> y(lgn + 1, 0);

    int x = 0;

    for (unsigned i = 1; i <= source.size(); i++)
    {
        y[0] ^= source[i - 1];
        x ^= source[i - 1] * i;
    }
    for (unsigned i = 1; i <= lgn; i++)
        y[i] = (x >> (lgn - i)) & 1;

    return y;
}

std::vector<int> retrieve(std::vector<int> data)
{
    unsigned const lgn = 31 - __builtin_clz(data.size());
    unsigned const n = 1 << lgn;
    int p = 0, x = 0;

    for (unsigned i = 1; i <= n - 1; i++)
    {
        p ^= data[i - 1];
        x ^= data[i - 1] * i;
    }

    if (p == data[n - 1])
        return std::vector<int>(data.begin(), data.begin() + n - 1);

    int y = 0;
    for (unsigned i = 0; i < lgn; i++)
        y = (y << 1) | data[n + i];

    data[(y ^ x) - 1] ^= 1;
    return std::vector<int>(data.begin(), data.begin() + n - 1);
}

• Subtask 1: 0 / 60
• Subtask 2: 0 / 40