Submission #679277

#	Time	Username	Problem	Language	Result	Execution time	Memory
679277		phoebe	Data Transfer (IOI19_transfer)	C++17	100 / 100	234 ms	2668 KiB

transfer

#include "transfer.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> get_attachment(vector<int> source){
    source.push_back(0);
    vector<int> re;
    for (int i = 1; i <= source.size(); i *= 2){
        int bruh = 0;
        int j = 0;
        while (j < source.size()){
            for (int k = 0; k < i; k++){
                bruh ^= source[j++];
            }
            j += i;
        }
        re.push_back(bruh);
    }
    return re;
}

vector<int> retrieve(vector<int> data){
    int sz = (data.size() == 63 + 7 ? 64 : 256);
    int x = 0;
    vector<int> re;
    for (int i = 0; i < sz - 1; i++){
        x ^= data[i];
        re.push_back(data[i]);
    }
    if (x == data.back()){
        return re;
    }
    re.push_back(0);
    int l = 0, r = sz, left_expected = data[data.size() - 2], idx = data.size() - 2;
    for (int k = sz / 2; k >= 1; k /= 2){
        // cout << l << ' ' << r << endl;
        int mid = (l + r) / 2; // [l, mid), [mid, r)
        int left = 0;
        for (int i = l; i < mid; i++) left ^= data[i];
        if (left == left_expected){ // not in range [l, mid)
            // cout << left << endl;
            l = mid;
        }
        else{ // not in range [mid, r)
            r = mid;
        }
        left_expected = data[--idx];
        if (k == 1) break;
        int j = 0;
        while (j < sz){
            for (int i = 0; i < k / 2; i++){
                if (j >= l && j < r) continue;
                left_expected ^= data[j++];
            }
            j += k / 2;
        }
    }
    // cout << endl << l << ' ' << r << endl;
    // for (auto x : re) cout << x; cout << endl;
    re[l] ^= 1;
    re.pop_back();
    return re;
}

Compilation message (stderr)

transfer.cpp: In function 'std::vector<int> get_attachment(std::vector<int>)':
transfer.cpp:8:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (int i = 1; i <= source.size(); i *= 2){
      |                     ~~^~~~~~~~~~~~~~~~
transfer.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         while (j < source.size()){
      |                ~~^~~~~~~~~~~~~~~

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