#include <bits/stdc++.h>
#include "communication.h"
using namespace std;
int answer[3][4] = {{0, 0, 0, 0}, {0, 1, 1, 0}, {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 <= 3; 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 = currLength / 3;
int idx = tracker.getIndex(x);
pair<int, int> recved = sendNumber(min(idx / setLength + 1, 3));
for (int i = 3; i >= 1; i--) {
int start = tracker.getElem(setLength * (i - 1));
int end = tracker.getElem(i == 3 ? 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 < 3; 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 = currLength / 3;
for (int i = 3; i >= 1; i--) {
int start = tracker.getElem(setLength * (i - 1));
int end = tracker.getElem(i == 3 ? 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 |
4 ms |
2744 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2740 KB |
Output is correct |
| 3 |
Correct |
7 ms |
2740 KB |
Output is correct |
| 4 |
Correct |
9 ms |
2740 KB |
Output is correct |
| 5 |
Correct |
5 ms |
2756 KB |
Output is correct |
| 6 |
Correct |
14 ms |
2820 KB |
Output is correct |
| 7 |
Correct |
24 ms |
2740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
540 ms |
2744 KB |
Output is partially correct |
| 2 |
Partially correct |
359 ms |
2716 KB |
Output is partially correct |
| 3 |
Partially correct |
336 ms |
2720 KB |
Output is partially correct |
| 4 |
Partially correct |
772 ms |
2724 KB |
Output is partially correct |
| 5 |
Partially correct |
677 ms |
2716 KB |
Output is partially correct |
| 6 |
Partially correct |
655 ms |
2752 KB |
Output is partially correct |
| 7 |
Partially correct |
2420 ms |
2788 KB |
Output is partially correct |
| 8 |
Partially correct |
3754 ms |
3024 KB |
Output is partially correct |
| 9 |
Partially correct |
3316 ms |
2920 KB |
Output is partially correct |
| 10 |
Partially correct |
3041 ms |
3264 KB |
Output is partially correct |
| 11 |
Partially correct |
3327 ms |
3188 KB |
Output is partially correct |
| 12 |
Partially correct |
3177 ms |
2960 KB |
Output is partially correct |
| 13 |
Partially correct |
3434 ms |
3340 KB |
Output is partially correct |
| 14 |
Partially correct |
3053 ms |
2936 KB |
Output is partially correct |
| 15 |
Partially correct |
1713 ms |
2780 KB |
Output is partially correct |
| 16 |
Partially correct |
3790 ms |
2856 KB |
Output is partially correct |
| 17 |
Partially correct |
931 ms |
2816 KB |
Output is partially correct |
| 18 |
Partially correct |
883 ms |
2784 KB |
Output is partially correct |
| 19 |
Partially correct |
866 ms |
2856 KB |
Output is partially correct |
| 20 |
Partially correct |
844 ms |
2780 KB |
Output is partially correct |
| 21 |
Partially correct |
902 ms |
2892 KB |
Output is partially correct |
| 22 |
Partially correct |
886 ms |
2784 KB |
Output is partially correct |
| 23 |
Partially correct |
1451 ms |
2860 KB |
Output is partially correct |
| 24 |
Correct |
3 ms |
2760 KB |
Output is correct |
| 25 |
Correct |
11 ms |
2736 KB |
Output is correct |
| 26 |
Correct |
12 ms |
2740 KB |
Output is correct |
| 27 |
Correct |
9 ms |
2740 KB |
Output is correct |
| 28 |
Correct |
4 ms |
2740 KB |
Output is correct |
| 29 |
Correct |
11 ms |
2964 KB |
Output is correct |
| 30 |
Correct |
18 ms |
2896 KB |
Output is correct |
