oj.uz

Submission #679277

# Submission time Handle Problem Language Result Execution time Memory
679277 2023-01-08T01:39:06 Z phoebe Data Transfer (IOI19_transfer) C++17
100 / 100
 234 ms 2668 KB 
#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

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.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 728 KB Output is correct
2 Correct 6 ms 648 KB Output is correct
3 Correct 4 ms 648 KB Output is correct
4 Correct 5 ms 648 KB Output is correct
5 Correct 4 ms 648 KB Output is correct
6 Correct 5 ms 728 KB Output is correct
7 Correct 5 ms 732 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 4 ms 648 KB Output is correct
10 Correct 6 ms 644 KB Output is correct
11 Correct 5 ms 644 KB Output is correct
12 Correct 7 ms 648 KB Output is correct
13 Correct 4 ms 648 KB Output is correct
14 Correct 5 ms 644 KB Output is correct
15 Correct 4 ms 648 KB Output is correct
16 Correct 5 ms 644 KB Output is correct
17 Correct 4 ms 640 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 2484 KB Output is correct
2 Correct 191 ms 2484 KB Output is correct
3 Correct 211 ms 2488 KB Output is correct
4 Correct 234 ms 2456 KB Output is correct
5 Correct 188 ms 2492 KB Output is correct
6 Correct 198 ms 2492 KB Output is correct
7 Correct 191 ms 2492 KB Output is correct
8 Correct 193 ms 2484 KB Output is correct
9 Correct 203 ms 2492 KB Output is correct
10 Correct 191 ms 2480 KB Output is correct
11 Correct 204 ms 2488 KB Output is correct
12 Correct 201 ms 2488 KB Output is correct
13 Correct 198 ms 2492 KB Output is correct
14 Correct 190 ms 2484 KB Output is correct
15 Correct 190 ms 2484 KB Output is correct
16 Correct 215 ms 2476 KB Output is correct
17 Correct 193 ms 2492 KB Output is correct
18 Correct 217 ms 2668 KB Output is correct
19 Correct 192 ms 2488 KB Output is correct