oj.uz

답안 #829961

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829961 2023-08-18T16:19:13 Z somethingnew Data Transfer (IOI19_transfer) C++17
100 / 100
 317 ms 2496 KB 
#include <iostream>

#include "algorithm"
#include "array"
#include "bitset"
#include "climits"
#include "cmath"
#include "deque"
#include "iomanip"
#include "map"
#include "numeric"
#include "set"
#include "transfer.h"
#include "vector"
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
vector<int> rearange(vector<int> a, int k) {
    int n = sz(a) - k;
    vector<int> b(sz(a));
    for (int i = 0; i < k; i++) {
        b[1 << i] = 1;
    }
    int ind = 0;
    for (int i = 0; i < sz(a) - k; i++) {
        while (b[ind] == 1) {
            ind++;
        }
        if (ind < sz(b)) {
            b[ind] = a[i];
            ind++;
        } else {
            cout << "FAC" << ind << endl;
        }
    }
    for (int i = 0; i < k; i++) {
        b[1 << i] = a[n + i];
    }
    return b;
}
vector<int> rearange2(vector<int> a, int k) {
    int n = sz(a) - k;
    vector<int> b(sz(a)), c = b;
    for (int i = 0; i < k; i++) {
        b[1 << i] = 1;
    }
    int ind = 0;
    for (int i = 0; i < sz(a) - k; i++) {
        while (ind < sz(b) and b[ind] == 1) {
            ind++;
        }
        if (ind < sz(c))
            c[i] = a[ind];
        else {
            cout << "BLYA" << ind << endl;
        }
        ind++;
    }
    for (int i = 0; i < k; i++) {
        c[n + i] = a[1 << i];
    }
    return c;
}
void addzer(vector<int> &a) {
    vector<int> b = {0};
    for (auto i : a) {
        b.push_back(i);
    }
    swap(a, b);
}
vector<int> get_attachment(vector<int> source) {
    addzer(source);
    int n = sz(source);
    int k = 7;
    if (n > 90)
        k = 9;
    vector<int> beba(k);
    for (int i = 0; i < k; i++) {
        source.push_back(0);
    }
    // for (auto i : source)
    //     cout << i;
    // cout << '\n';
    source = rearange(source, k);
    // source = rearange2(source, k);
    // for (auto i : source)
    //    cout << i;
    // cout << '\n';
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n + k; j++) {
            if (j & (1 << i))
                beba[i] ^= source[j];
        }
    }
    return beba;
}
vector<int> retrieve(vector<int> data) {
    addzer(data);
    int n = sz(data);
    int k = 7;
    if (n > 90)
        k = 9;
    n -= k;
    for (int i = n; i < n + k; i++) {
        // data[i] = 2 + i - n;
    }

    // for (auto i : data)
    //     cout << i;
    //  cout << '\n';
    data = rearange(data, k);
    // for (auto i : data)
    //     cout << i;
    //  cout << '\n';
    //   cout << n << ' ' << k << '\n';
    vector<int> beba(k);
    int ind = 0;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n + k; j++) {
            if (j & (1 << i))
                beba[i] ^= data[j];
        }
        if (beba[i] != 0)
            ind += (1 << i);
    }
    // cerr << ind << endl;
    //  exit(0);
    data[ind] ^= 1;

    data = rearange2(data, k);
    vector<int> res;
    for (int i = 1; i < n; i++) {
        res.push_back(data[i]);
        // cout << data[i];
    }
    // cout << endl;
    return res;
}

#ifdef LOCAL

static inline string run_scenario() {
    int c;
    cin >> c;
    if (c < -1)
        return "invalid corruption index";
    string source_str;
    cin >> source_str;
    const int N = source_str.size();
    const int max_attachment_size = 2 * N;
    vector<int> source;
    for (int i = 0; i < N; i++)
        source.push_back(source_str[i] - '0');

    vector<int> attachment = get_attachment(source);
    if (int(attachment.size()) > max_attachment_size)
        return "attachment too large";
    for (int x : attachment)
        if (x != 0 && x != 1)
            return "invalid attachment integer value";

    vector<int> data(source);
    data.insert(data.end(), attachment.begin(), attachment.end());

    if (c >= int(data.size()))
        return "invalid corruption index";

    if (c >= 0)
        data[c] = 1 - data[c];

    vector<int> result_source = retrieve(data);

    if (source != result_source)
        return "wrong source retrieval";

    return string("OK K=") + to_string(attachment.size());
}

int main() {
    freopen("inp.txt", "r", stdin);
    int T;
    cin >> T;
    for (int scenario = 0; scenario < T; scenario++) {
        string result = run_scenario();
        cout << "scenario #" << scenario << ": " << result << endl;
    }
    return 0;
}
#endif

Subtask #1
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 8 ms 724 KB Output is correct
3 Correct 6 ms 648 KB Output is correct
4 Correct 6 ms 732 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 6 ms 640 KB Output is correct
8 Correct 7 ms 592 KB Output is correct
9 Correct 7 ms 640 KB Output is correct
10 Correct 6 ms 732 KB Output is correct
11 Correct 6 ms 648 KB Output is correct
12 Correct 6 ms 640 KB Output is correct
13 Correct 6 ms 720 KB Output is correct
14 Correct 6 ms 652 KB Output is correct
15 Correct 6 ms 648 KB Output is correct
16 Correct 6 ms 652 KB Output is correct
17 Correct 6 ms 640 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 2488 KB Output is correct
2 Correct 300 ms 2492 KB Output is correct
3 Correct 317 ms 2496 KB Output is correct
4 Correct 287 ms 2484 KB Output is correct
5 Correct 295 ms 2496 KB Output is correct
6 Correct 291 ms 2488 KB Output is correct
7 Correct 296 ms 2488 KB Output is correct
8 Correct 293 ms 2488 KB Output is correct
9 Correct 289 ms 2492 KB Output is correct
10 Correct 299 ms 2492 KB Output is correct
11 Correct 288 ms 2484 KB Output is correct
12 Correct 301 ms 2428 KB Output is correct
13 Correct 304 ms 2496 KB Output is correct
14 Correct 291 ms 2492 KB Output is correct
15 Correct 289 ms 2480 KB Output is correct
16 Correct 291 ms 2484 KB Output is correct
17 Correct 301 ms 2484 KB Output is correct
18 Correct 306 ms 2488 KB Output is correct
19 Correct 292 ms 2484 KB Output is correct