oj.uz

Submission #529004

# Submission time Handle Problem Language Result Execution time Memory
529004 2022-02-21T21:35:44 Z tabr Data Transfer (IOI19_transfer) C++17
100 / 100
 76 ms 2480 KB 
#ifndef tabr
#include "transfer.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
 
vector<int> get_attachment(vector<int> a) {
    int n = (int) a.size();
    int q = __builtin_popcount(n);
    int c = 0;
    for (int i = 0; i < n; i++) {
        if (a[i]) {
            c ^= i + 1;
        }
    }
    for (int i = 0; i < (1 << (q + 1)); i++) {
        if (__builtin_parity(i) == 0) {
            if (c == 0) {
                vector<int> b;
                for (int j = 0; j < q + 1; j++) {
                    if (i & (1 << j)) {
                        b.emplace_back(1);
                    } else {
                        b.emplace_back(0);
                    }
                }
                return b;
            }
            c--;
        }
    }
    return vector<int>();
}
 
vector<int> retrieve(vector<int> a) {
    int n = 1;
    int q = 1;
    while (n + q + 1 < (int) a.size()) {
        n *= 2;
        n++;
        q++;
    }
    int c = 0;
    for (int i = n; i < n + q + 1; i++) {
        c ^= a[i] << (i - n);
    }
    a.resize(n);
    if (__builtin_parity(c) == 1) {
        return a;
    }
    int b = 0;
    for (int i = 0; i < c; i++) {
        if (__builtin_parity(i) == 0) {
            b++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (a[i]) {
            b ^= i + 1;
        }
    }
    if (b > 0) {
        a[b - 1] ^= 1;
    }
    return a;
}
 
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
 
int rand_int(int a, int b) {  // [a, b]
    return uniform_int_distribution<int>(a, b)(rng);
}
 
#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n = 7;
    int tt = 1000;
    while (tt--) {
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            a[i] = rand_int(0, 1);
        }
        auto b = get_attachment(a);
        int pos = rand_int(-1, (int) b.size() - 1);
        if (pos >= 0) {
            b[pos] ^= 1;
        }
        auto c = retrieve(b);
        if (a == c) {
            // cerr << "OK" << endl;
        } else {
            cerr << "NG" << endl;
            debug(pos);
            debug(a);
            debug(b);
            debug(c);
        }
    }
    return 0;
}
#endif

Subtask #1
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 564 KB Output is correct
2 Correct 3 ms 712 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 3 ms 680 KB Output is correct
5 Correct 3 ms 684 KB Output is correct
6 Correct 4 ms 628 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 704 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Correct 4 ms 708 KB Output is correct
12 Correct 3 ms 620 KB Output is correct
13 Correct 3 ms 628 KB Output is correct
14 Correct 3 ms 720 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 2 ms 756 KB Output is correct
17 Correct 3 ms 692 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2472 KB Output is correct
2 Correct 69 ms 2476 KB Output is correct
3 Correct 61 ms 2344 KB Output is correct
4 Correct 60 ms 2468 KB Output is correct
5 Correct 76 ms 2476 KB Output is correct
6 Correct 67 ms 2440 KB Output is correct
7 Correct 63 ms 2476 KB Output is correct
8 Correct 65 ms 2428 KB Output is correct
9 Correct 55 ms 2472 KB Output is correct
10 Correct 55 ms 2468 KB Output is correct
11 Correct 53 ms 2420 KB Output is correct
12 Correct 67 ms 2428 KB Output is correct
13 Correct 61 ms 2468 KB Output is correct
14 Correct 60 ms 2448 KB Output is correct
15 Correct 58 ms 2428 KB Output is correct
16 Correct 57 ms 2472 KB Output is correct
17 Correct 62 ms 2468 KB Output is correct
18 Correct 60 ms 2432 KB Output is correct
19 Correct 58 ms 2480 KB Output is correct