제출 #668696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
668696		finn__	Data Transfer (IOI19_transfer)	C++17	100 / 100	52 ms	2504 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];

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

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