이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "communication.h"
using namespace std;
//
// --- Sample implementation for the task communication ---
//
// To compile this program with the sample grader, place:
// communication.h communication_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
// g++ -std=c++17 communication_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//
struct Seg{
int l, r;
bool operator < (const Seg &sc) const{
if(l == sc.l) return r < sc.r;
else return l < sc.l;
}
};
vector<Seg> merge(vector<Seg> a, vector<Seg> b){
for(auto seg : b) a.push_back(seg);
return a;
}
vector<Seg> fix(vector<Seg> vec){
sort(vec.begin(), vec.end());
vector<Seg> ans;
for(auto seg : vec){
if(ans.empty() || seg.l != ans.back().r + 1) ans.push_back(seg);
else ans.back().r = seg.r;
}
return ans;
}
bool isin(vector<Seg> vec, int x){
for(auto seg : vec) if(x >= seg.l && x <= seg.r) return true;
return false;
}
int len(vector<Seg> vec){
int ans = 0;
for(auto seg : vec) ans += seg.r - seg.l + 1;
return ans;
}
bool isgood(string str){
if(str[0] == '0' && str[1] == '0') return false;
else if(str[1] == '0' && str[2] == '0') return false;
else if(str[2] == '0' && str[3] == '0') return false;
else return true;
}
vector<int> tokeep(string str){
vector<int> ans;
string truth;
// 1 0 0 0
truth += str[0] == '1' ? '1' : '0';
truth += str[1] == '0' ? '1' : '0';
truth += str[2] == '0' ? '1' : '0';
truth += str[3] == '0' ? '1' : '0';
if(isgood(truth)) ans.push_back(0);
// 0 1 0 0
truth = "";
truth += str[0] == '0' ? '1' : '0';
truth += str[1] == '1' ? '1' : '0';
truth += str[2] == '1' ? '1' : '0';
truth += str[3] == '0' ? '1' : '0';
if(isgood(truth)) ans.push_back(1);
// 0 0 1 0
truth = "";
truth += str[0] == '0' ? '1' : '0';
truth += str[1] == '0' ? '1' : '0';
truth += str[2] == '0' ? '1' : '0';
truth += str[3] == '1' ? '1' : '0';
if(isgood(truth)) ans.push_back(2);
// 0 0 0 1
truth = "";
truth += str[0] == '1' ? '1' : '0';
truth += str[1] == '1' ? '1' : '0';
truth += str[2] == '1' ? '1' : '0';
truth += str[3] == '1' ? '1' : '0';
if(isgood(truth)) ans.push_back(3);
return ans;
}
void encode(int n, int x) {
vector<Seg> segments = {{1, n}};
while(len(segments) > 3){
vector<Seg> parts[4];
int req = len(segments) / 4;
int cur = 0, cursum = 0;
for(int i = 0; i < segments.size(); i++){
if(cur == 3 || cursum + (segments[i].r - segments[i].l + 1) <= req){
parts[cur].push_back(segments[i]);
cursum += (segments[i].r - segments[i].l + 1);
}
else{
if(cursum < req){
parts[cur].push_back({segments[i].l, segments[i].l + (req - cursum) - 1});
segments[i].l = segments[i].l + (req - cursum);
}
cur++, cursum = 0;
i--;
}
}
string answers;
answers += '0' + (send(isin(parts[0], x) || isin(parts[3], x)));
answers += '0' + (send(isin(parts[1], x) || isin(parts[3], x)));
answers += '0' + (send(isin(parts[1], x) || isin(parts[3], x)));
answers += '0' + (send(isin(parts[2], x) || isin(parts[3], x)));
vector<int> keep = tokeep(answers);
assert(keep.size() == 2);
segments = merge(parts[keep[0]], parts[keep[1]]);
segments = fix(segments);
}
if(len(segments) == 3){
vector<int> nums(3);
if(segments.size() == 1){
nums[0] = segments[0].l;
nums[1] = segments[0].l + 1;
nums[2] = segments[0].l + 2;
}
else if(segments.size() == 2){
if(segments[0].l == segments[0].r){
nums[0] = segments[0].l;
nums[1] = segments[1].l;
nums[2] = segments[1].l + 1;
}
else{
nums[0] = segments[0].l;
nums[1] = segments[0].l + 1;
nums[2] = segments[1].l;
}
}
else{
nums[0] = segments[0].l;
nums[1] = segments[1].l;
nums[2] = segments[2].l;
}
send(nums[0] == x || nums[2] == x);
send(nums[1] == x || nums[2] == x);
send(nums[1] == x || nums[2] == x);
send(nums[2] == x);
}
}
pair<int, int> decode(int n) {
vector<Seg> segments = {{1, n}};
while(len(segments) > 3){
vector<Seg> parts[4];
int req = len(segments) / 4;
int cur = 0, cursum = 0;
for(int i = 0; i < segments.size(); i++){
if(cur == 3 || cursum + (segments[i].r - segments[i].l + 1) <= req){
parts[cur].push_back(segments[i]);
cursum += (segments[i].r - segments[i].l + 1);
}
else{
if(cursum < req){
parts[cur].push_back({segments[i].l, segments[i].l + (req - cursum) - 1});
segments[i].l = segments[i].l + (req - cursum);
}
cur++, cursum = 0;
i--;
}
}
string answers;
answers += '0' + receive();
answers += '0' + receive();
answers += '0' + receive();
answers += '0' + receive();
vector<int> keep = tokeep(answers);
assert(keep.size() == 2);
segments = merge(parts[keep[0]], parts[keep[1]]);
segments = fix(segments);
}
if(len(segments) == 1) return {segments[0].l, segments[0].l};
else if(len(segments) == 2){
if(segments.size() == 1) return {segments[0].l, segments[0].l + 1};
else{
return {segments[0].l, segments[1].l};
}
}
if(len(segments) == 3){
vector<int> nums(3);
if(segments.size() == 1){
nums[0] = segments[0].l;
nums[1] = segments[0].l + 1;
nums[2] = segments[0].l + 2;
}
else if(segments.size() == 2){
if(segments[0].l == segments[0].r){
nums[0] = segments[0].l;
nums[1] = segments[1].l;
nums[2] = segments[1].l + 1;
}
else{
nums[0] = segments[0].l;
nums[1] = segments[0].l + 1;
nums[2] = segments[1].l;
}
}
else{
nums[0] = segments[0].l;
nums[1] = segments[1].l;
nums[2] = segments[2].l;
}
string answers;
answers += '0' + receive();
answers += '0' + receive();
answers += '0' + receive();
answers += '0' + receive();
vector<int> ans;
string truth;
// 1 0 0
truth += answers[0] == '1' ? '1' : '0';
truth += answers[1] == '0' ? '1' : '0';
truth += answers[2] == '0' ? '1' : '0';
truth += answers[3] == '0' ? '1' : '0';
if(isgood(truth)) ans.push_back(0);
// 0 1 0
truth = "";
truth += answers[0] == '0' ? '1' : '0';
truth += answers[1] == '1' ? '1' : '0';
truth += answers[2] == '1' ? '1' : '0';
truth += answers[3] == '0' ? '1' : '0';
if(isgood(truth)) ans.push_back(1);
// 0 0 1
truth = "";
truth += answers[0] == '1' ? '1' : '0';
truth += answers[1] == '1' ? '1' : '0';
truth += answers[2] == '1' ? '1' : '0';
truth += answers[3] == '1' ? '1' : '0';
if(isgood(truth)) ans.push_back(2);
if(ans.size() == 1) return {nums[ans[0]], nums[ans[0]]};
else return {nums[ans[0]], nums[ans[1]]};
}
}
컴파일 시 표준 에러 (stderr) 메시지
communication.cpp: In function 'void encode(int, int)':
communication.cpp:126:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for(int i = 0; i < segments.size(); i++){
| ~~^~~~~~~~~~~~~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:201:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | for(int i = 0; i < segments.size(); i++){
| ~~^~~~~~~~~~~~~~~~~
communication.cpp:192:35: warning: control reaches end of non-void function [-Wreturn-type]
192 | vector<Seg> segments = {{1, n}};
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |