Submission #1006240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006240		AliMark71	Data Transfer (IOI19_transfer)	C++17	100 / 100	36 ms	2520 KiB

transfer

#include "transfer.h"

using namespace std;

std::vector<int> get_attachment(std::vector<int> source) {
    int xorSum = 0;
    for (int i = 0; i < source.size(); i++) if (source[i]) xorSum ^= (i + 1);
    
    int correctionSize = __builtin_popcount((int) source.size());
    
    vector<int> correctionData(correctionSize + 1);
    for (int i = 0; i < correctionSize; i++) if (xorSum&(1<<i)) correctionData[i] = 1;
    correctionData.back() = __builtin_popcount(xorSum) % 2;
    
    return correctionData;
}

std::vector<int> retrieve(std::vector<int> data) {
    int baseSize = (data.size() == 70 ? 6 : 8);
    
    vector<int> possibleSource(data.begin(), data.begin() + (1<<baseSize) - 1);
    vector<int> correctionData(data.begin() + possibleSource.size(), data.end());
    
    int correctionPopCount = 0;
    for (int i = 0; i < correctionData.size() - 1; i++) correctionPopCount += correctionData[i];
    
    if (correctionPopCount % 2 == correctionData.back()) {
        int checkSum = 0;
        for (int i = 0, val = 1; i < correctionData.size() - 1; i++, val *= 2) checkSum += correctionData[i] * val;
             
        int expectedCheckSum = 0;
        for (int i = 0; i < possibleSource.size(); i++) if (possibleSource[i]) expectedCheckSum ^= (i + 1);
        
        if (checkSum != expectedCheckSum) {
            int errorPos = checkSum ^ expectedCheckSum;
            possibleSource[errorPos - 1] ^= 1;
        }
    }

    return possibleSource;
}

Compilation message (stderr)

transfer.cpp: In function 'std::vector<int> get_attachment(std::vector<int>)':
transfer.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < source.size(); i++) if (source[i]) xorSum ^= (i + 1);
      |                     ~~^~~~~~~~~~~~~~~
transfer.cpp: In function 'std::vector<int> retrieve(std::vector<int>)':
transfer.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0; i < correctionData.size() - 1; i++) correctionPopCount += correctionData[i];
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
transfer.cpp:29:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int i = 0, val = 1; i < correctionData.size() - 1; i++, val *= 2) checkSum += correctionData[i] * val;
      |                                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
transfer.cpp:32:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i = 0; i < possibleSource.size(); i++) if (possibleSource[i]) expectedCheckSum ^= (i + 1);
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~

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