Submission #1038473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038473		farkon00	Data Transfer (IOI19_transfer)	C++14	0 / 100	4 ms	2512 KiB

transfer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma GCC optimize("O3")
#define all(a) (a).begin(), (a).end()
#define ull unsigned long long
#define ll long long
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_ll;
typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_p;

ll ceil_div(ll a, ll b) {
    if (a % b == 0) return a / b;
    else return a / b + 1;
}

struct splitmix_hash {
public:
    size_t operator()(ull x) const {
        static const ull FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x += FIXED_RANDOM;
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
};

struct pairhash {
public:
    template <typename T, typename U>
    std::size_t operator()(const std::pair<T, U> &x) const {
        int n = std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
        return splitmix_hash()(n);
    }
};

#define MOD 1000000007

ll bin_pow(ll a, ll p) {
    vector<ll> powers(31);
    powers[1] = a;
    for (int i = 2; i < 31; i++) {
        powers[i] = (powers[i - 1] * powers[i - 1]) % MOD;
    }
    int s = 0;
    ll res = 1;
    while (p >> s) {
        if ((p >> s) & 1) res = (res * powers[s + 1]) % MOD;
        s++;
    }
    return res;
}

// vector<ll> fact(1e6 + 1), rev_fact(1e6 + 1);

// ll choose(ll k, ll n) {
//     if (k > n) return 0;
//     return ((fact[n] * rev_fact[k]) % MOD * rev_fact[n - k]) % MOD;
// }

#include "transfer.h"

vector<int> get_attachment(vector<int> source) {
    int l = 0;
    while (source.size() >> l) l++;
	vector<int> res(l + 1);
    for (int i = 1; i <= source.size(); i++) {
        for (int s = 0; s < l; s++) {
            if ((i >> s) & 1) res[s] ^= source[i];
        }
        res[l] ^= source[i];
    }
    return res;
}

vector<int> retrieve(vector<int> data) {
    int l;
    if (data.size() == 70) l = 6;
    else l = 8;

    vector<int> res(l + 1), expected(data.end() - l - 1, data.end());
    data.resize(data.size() - l - 1);
    for (int i = 1; i < data.size(); i++) {
        for (int s = 0; s < l; s++) {
            if ((i >> s) & 1) res[s] ^= data[i];
        }
        res[l] ^= data[i];
    }
    if (res[l] == expected[l]) return data;
    int swapped = 0;
    for (int s = 0; s < l; s++) {
        if (res[s] != expected[s]) swapped |= 1 << s;
    }
    if (swapped == 0) return data;
    data[swapped - 1] ^= 1;
    return data;
}

Compilation message (stderr)

transfer.cpp: In function 'std::vector<int> get_attachment(std::vector<int>)':
transfer.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 1; i <= source.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
transfer.cpp: In function 'std::vector<int> retrieve(std::vector<int>)':
transfer.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 1; i < data.size(); i++) {
      |                     ~~^~~~~~~~~~~~~

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