| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1310905 | theiulius | Data Transfer (IOI19_transfer) | C++20 | 0 ms | 0 KiB |
#include "transfer.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
std::vector<int> get_attachment(std::vector<int> a) {
vector<int> v;
int n = a.size();
for (int k = 5; k >= 0; k--){
int i = 0;
int ans = 0;
while (i < n){
for (int j = i; j < min(n, i + (1 << k)); j++){
ans ^= a[j];
}
i += 2 * (1 << k);
}
v.pb(ans);
}
int ans = 0;
for (int i = 0; i < n; i++){
ans ^= a[i];
}
v.pb(ans);
// for (auto h : v){
// cout << h;
// }
// cout << endl;
return v;
}
std::vector<int> retrieve(std::vector<int> a) {
int n = a.size() - 7;
int K = 7;
int ans0 = 0;
for (int i = 0; i < n; i++){
// cout << a[i];
ans0 ^= a[i];
}
// cout << endl;
int l = 0, r = 63;
for (int k = 5; k >= 0; k--){
int i = 0;
int ans = 0;
while (i < n){
for (int j = i; j < min(n, i + (1 << k)); j++){
ans ^= a[j];
}
i += 2 * (1 << k);
}
// cout << l << " " << r << endl;
if (a[n + (5 - k)] != ans){ // pirvel naxevarshia
if (ans0 != a[n + K - 1]){ // n-shia corrupted
r = (l + r) / 2;
}else{
a.resize(n);
return a;
}
}else{ // meore naxevarshia
if (ans0 != a[n + K - 1]){ // n-shia corrupted
l = (l + r + 1) / 2;
}
}
}
// cout << l << " " << r << endl;
a[l] ^= 1;
a.pop_back();
a.pop_back();
a.pop_back();
a.pop_back();
a.pop_back();
a.pop_back();
a.pop_back();
return a;
// 011001010110110110100111110011010111111111111000101011100101001
// 011001010110110110100111110011010111111111111000101011100101001
}
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);
// for (int h : source){
// cout << h;
// }
// cout << endl;
// for (int h : result_source){
// cout << h;
// }
// cout << endl;
if (source != result_source)
return "wrong source retrieval";
return string("OK K=")+to_string(attachment.size());
}
main() {
int T;
cin >> T;
for (int scenario = 0; scenario < T; scenario++) {
string result = run_scenario();
cout << "scenario #" << scenario << ": " << result << endl;
}
return 0;
}