oj.uz

Submission #369887

# Submission time Handle Problem Language Result Execution time Memory
369887 2021-02-22T17:15:59 Z wiwiho Data Transfer (IOI19_transfer) C++14
100 / 100
 616 ms 2908 KB 
#include "transfer.h"

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) (((a) + (b) - 1) / (b))
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

vector<int> msk;

void build(int k){
    msk.clear();
    for(int i = 0; i < (1 << k); i++){
        if(__builtin_popcount(i) > 1) msk.eb(i);
    }
}

vector<int> get_attachment(vector<int> source){

    int k = source.size() == 63 ? 7 : 9;
    build(k);

    vector<int> ans(k);
    for(int i = 0; i < source.size(); i++){
        int t = msk[i];
        for(int j = 0; j < k; j++){
            if(1 << j & t) ans[j] ^= source[i];
        }
    }

//    printv(ans, cerr);
//    for(int i : ans) cerr << i;
//    cerr << "\n";

    return ans;
}

vector<int> retrieve(vector<int> data){

//    for(int i : data) cerr << i;
//    cerr << "\n";

    int n = data.size() == 70 ? 63 : 255;
    int k = data.size() - n;
    build(k);

    vector<int> c(k);
    for(int i = 0; i < n; i++){
        int t = msk[i];
        for(int j = 0; j < k; j++){
            if(1 << j & t) c[j] ^= data[i];
        }
    }
//    printv(c, cerr);
//    cerr << msk[0] << "\n";

    int ans = 0;
    for(int i = 0; i < k; i++){
        if(data[n + i] != c[i]) ans |= 1 << i;
    }
//    cerr << ans << "\n";
    if(__builtin_popcount(ans) > 1){
        for(int i = 0; i < n; i++){
            if(msk[i] == ans){
//            cerr << "qaq " << i << "\n";
                data[i] ^= 1;
            }
        }
    }

    vector<int> owo(n);
    for(int i = 0; i < n; i++) owo[i] = data[i];
//    for(int i : owo) cerr << i;
//    cerr << "\n";

    return owo;

}

Compilation message

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

Subtask #1
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1088 KB Output is correct
2 Correct 9 ms 1008 KB Output is correct
3 Correct 9 ms 1088 KB Output is correct
4 Correct 9 ms 880 KB Output is correct
5 Correct 9 ms 1008 KB Output is correct
6 Correct 9 ms 920 KB Output is correct
7 Correct 9 ms 1136 KB Output is correct
8 Correct 9 ms 880 KB Output is correct
9 Correct 12 ms 880 KB Output is correct
10 Correct 9 ms 1048 KB Output is correct
11 Correct 9 ms 920 KB Output is correct
12 Correct 9 ms 1008 KB Output is correct
13 Correct 9 ms 920 KB Output is correct
14 Correct 9 ms 832 KB Output is correct
15 Correct 9 ms 1344 KB Output is correct
16 Correct 9 ms 1008 KB Output is correct
17 Correct 9 ms 1036 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 2724 KB Output is correct
2 Correct 575 ms 2604 KB Output is correct
3 Correct 574 ms 2612 KB Output is correct
4 Correct 577 ms 2644 KB Output is correct
5 Correct 585 ms 2604 KB Output is correct
6 Correct 610 ms 2612 KB Output is correct
7 Correct 572 ms 2604 KB Output is correct
8 Correct 584 ms 2648 KB Output is correct
9 Correct 578 ms 2468 KB Output is correct
10 Correct 612 ms 2908 KB Output is correct
11 Correct 591 ms 2656 KB Output is correct
12 Correct 588 ms 2604 KB Output is correct
13 Correct 580 ms 2744 KB Output is correct
14 Correct 616 ms 2604 KB Output is correct
15 Correct 601 ms 2468 KB Output is correct
16 Correct 579 ms 2596 KB Output is correct
17 Correct 590 ms 2596 KB Output is correct
18 Correct 604 ms 2596 KB Output is correct
19 Correct 607 ms 2596 KB Output is correct