#include <bits/stdc++.h>
#include "communication.h"
using namespace std;
int answer[4][4] = {{0, 0, 0, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 1, 1, 1}};
int corruptible(int* a, int* b, int size) {
bool canCorrupt = true;
for (int i = 0; i < size; i++) {
if (a[i] != b[i]) {
if (!canCorrupt) return false;
canCorrupt = false;
} else {
canCorrupt = true;
}
}
return true;
}
struct Tracker {
vector<pair<int, int>> ranges;
Tracker(int n) {
ranges.emplace_back(1, n);
}
int totalLength() {
int res = 0;
for (auto& p: ranges) {
res += p.second - p.first + 1;
}
return res;
}
int getIndex(int val) {
int extra = 0;
for (auto& p: ranges) {
if (val >= p.first && val <= p.second) {
return extra + (val - p.first);
}
extra += p.second - p.first + 1;
}
cerr << "ERROR" << endl;
return 0;
}
int getElem(int idx) {
for (auto& p: ranges) {
int length = p.second - p.first + 1;
if (idx < length) {
return p.first + idx;
} else {
idx -= length;
}
}
cerr << "ERROR" << endl;
return 1;
}
void removeRange(int start, int end) {
vector<pair<int, int>> res;
for (auto& p: ranges) {
if (p.second < start || p.first > end) {
res.push_back(p);
} else {
if (start <= p.first && p.second <= end) continue;
else if (start <= p.first) res.push_back({end + 1, p.second});
else if (p.second <= end) res.push_back({p.first, start - 1});
else {
res.push_back({p.first, start - 1});
res.push_back({end + 1, p.second});
}
}
}
ranges.swap(res);
}
void print() {
for (auto& p: ranges) {
cout << "[" << p.first << " " << p.second << "] ";
}
cout << endl;
}
};
pair<int, int> sendNumber(int num) {
int res[4];
for (int i = 0; i < 4; i++) {
res[i] = send(answer[num-1][i]);
}
int other = num;
for (int i = 1; i <= 4; i++) {
if (i == num) continue;
if (corruptible(res, answer[i-1], 4)) {
other = i;
break;
}
}
return {min(other, num), max(other, num)};
}
void encode(int n, int x) {
Tracker tracker(n);
while (tracker.totalLength() > 2) {
int currLength = tracker.totalLength();
//cout << "Length = " << currLength << endl;
int setLength = max(1, currLength / 4);
int idx = tracker.getIndex(x);
pair<int, int> recved = sendNumber(min(idx / setLength + 1, 4));
for (int i = min(4, currLength); i >= 1; i--) {
int start = tracker.getElem(setLength * (i - 1));
int end = tracker.getElem(i == 4 ? currLength - 1 : setLength * i - 1);
if (i != recved.first && i != recved.second) {
//cout << "Removing range " << start << " " << end << endl;
tracker.removeRange(start, end);
}
}
//tracker.print();
}
}
pair<int, int> decode(int n) {
Tracker tracker(n);
while (tracker.totalLength() > 2) {
int res[4];
for (int i = 0; i < 4; i++) {
res[i] = receive();
}
vector<int> nums;
for (int i = 0; i < 4; i++) {
if (corruptible(res, answer[i], 4)) {
nums.push_back(i + 1);
}
}
nums.push_back(nums[0]);
int a = nums[0];
int b = nums[1];
int currLength = tracker.totalLength();
int setLength = max(currLength / 4, 1);
for (int i = min(4, currLength); i >= 1; i--) {
int start = tracker.getElem(setLength * (i - 1));
int end = tracker.getElem(i == 4 ? currLength - 1 : setLength * i - 1);
if (i != a && i != b) {
//cout << "Removing range " << start << " " << end << endl;
tracker.removeRange(start, end);
}
}
//tracker.print();
}
return {tracker.getElem(0), tracker.getElem(1)};
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
2740 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2756 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2736 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2740 KB |
Output is correct |
| 5 |
Correct |
7 ms |
2736 KB |
Output is correct |
| 6 |
Correct |
10 ms |
2844 KB |
Output is correct |
| 7 |
Correct |
21 ms |
2984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
480 ms |
2716 KB |
Output is partially correct |
| 2 |
Partially correct |
226 ms |
2848 KB |
Output is partially correct |
| 3 |
Partially correct |
278 ms |
2724 KB |
Output is partially correct |
| 4 |
Partially correct |
525 ms |
2720 KB |
Output is partially correct |
| 5 |
Partially correct |
442 ms |
2916 KB |
Output is partially correct |
| 6 |
Partially correct |
359 ms |
2716 KB |
Output is partially correct |
| 7 |
Partially correct |
1498 ms |
2804 KB |
Output is partially correct |
| 8 |
Partially correct |
2183 ms |
2900 KB |
Output is partially correct |
| 9 |
Partially correct |
1648 ms |
2932 KB |
Output is partially correct |
| 10 |
Partially correct |
1802 ms |
3028 KB |
Output is partially correct |
| 11 |
Partially correct |
2115 ms |
2924 KB |
Output is partially correct |
| 12 |
Partially correct |
1651 ms |
2944 KB |
Output is partially correct |
| 13 |
Partially correct |
1754 ms |
2948 KB |
Output is partially correct |
| 14 |
Partially correct |
1972 ms |
2924 KB |
Output is partially correct |
| 15 |
Partially correct |
1014 ms |
2792 KB |
Output is partially correct |
| 16 |
Partially correct |
2410 ms |
2960 KB |
Output is partially correct |
| 17 |
Partially correct |
493 ms |
2796 KB |
Output is partially correct |
| 18 |
Partially correct |
525 ms |
3040 KB |
Output is partially correct |
| 19 |
Partially correct |
479 ms |
2868 KB |
Output is partially correct |
| 20 |
Partially correct |
536 ms |
2876 KB |
Output is partially correct |
| 21 |
Partially correct |
585 ms |
2788 KB |
Output is partially correct |
| 22 |
Partially correct |
533 ms |
3060 KB |
Output is partially correct |
| 23 |
Partially correct |
953 ms |
2888 KB |
Output is partially correct |
| 24 |
Correct |
4 ms |
2976 KB |
Output is correct |
| 25 |
Correct |
4 ms |
2732 KB |
Output is correct |
| 26 |
Correct |
6 ms |
2764 KB |
Output is correct |
| 27 |
Correct |
6 ms |
2784 KB |
Output is correct |
| 28 |
Correct |
11 ms |
2740 KB |
Output is correct |
| 29 |
Correct |
12 ms |
3240 KB |
Output is correct |
| 30 |
Correct |
18 ms |
2748 KB |
Output is correct |
