Submission #711024

#	Time	Username	Problem	Language	Result	Execution time	Memory
711024		becaido	Data Transfer (IOI19_transfer)	C++17	100 / 100	342 ms	2500 KiB

transfer

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

vector<int> get_attachment(vector<int> source) {
	int n = source.size(), m = __lg(n + 1);
	vector<int> val(m + 1);
	for (int i = 1; i <= n; i++) if (source[i - 1]) {
        for (int j = 0; j < m; j++) if (i >> j & 1) val[j + 1] ^= 1;
        if (__builtin_popcount(i) == 1) val[0] ^= 1;
	}
	return val;
}

vector<int> differ(vector<int> a, vector<int> b) {
    vector<int> p;
    for (int i = 0; i < a.size(); i++) if (a[i] != b[i]) p.emplace_back(i);
    return p;
}

vector<int> retrieve(vector<int> data) {
    int n = (data.size() == 70 ? 63 : 255), m = __lg(n + 1);
    vector<int> val;
    while (data.size() > n) {
        val.emplace_back(data.back());
        data.pop_back();
    }
    reverse(val.begin(), val.end());
    auto p = differ(get_attachment(data), val);
    if (p.size() <= 1) return data;
    int mask = 0;
    for (int i : p) if (i) mask |= 1 << i - 1;
    data[mask - 1] ^= 1;
    return data;
}

Compilation message (stderr)

transfer.cpp: In function 'std::vector<int> differ(std::vector<int>, std::vector<int>)':
transfer.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < a.size(); i++) if (a[i] != b[i]) p.emplace_back(i);
      |                     ~~^~~~~~~~~~
transfer.cpp: In function 'std::vector<int> retrieve(std::vector<int>)':
transfer.cpp:24:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     while (data.size() > n) {
      |            ~~~~~~~~~~~~^~~
transfer.cpp:32:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   32 |     for (int i : p) if (i) mask |= 1 << i - 1;
      |                                         ~~^~~
transfer.cpp:22:45: warning: unused variable 'm' [-Wunused-variable]
   22 |     int n = (data.size() == 70 ? 63 : 255), m = __lg(n + 1);
      |                                             ^

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