QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#428714 | #7281. How to Avoid Disqualification in 75 Easy Steps | Crafticat# | 0 | 131ms | 4848kb | C++14 | 5.3kb | 2024-06-01 21:05:40 | 2024-06-01 21:05:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
std::vector<int> wait();
void send(std::vector<int>);
using pii = pair<int,int>;
vector<int> toVec(set<int> &s) {
vector<int> t(s.begin(),s.end());
return t;
}
int gen(int a, int b) {
return a + rand() % (b - a + 1);
std::random_device r;
std::default_random_engine e1(r());
std::uniform_int_distribution<int> uniform_dist(a, b);
int x = uniform_dist(e1);
return x;
}
//768 876
std::pair<int, int> scout(int R, int H) {
int Z = 500;
int T = 20;
srand(2);
set<int> pos;
for (int i = 1; i <= 1000; ++i) {
pos.insert(i);
}
vector<vector<int>> q(T), qR(T);
vector<set<int>> qSet(T), qRSet(T);
for (int i = 0; i < T; ++i) {
set<int> s;
set<int> notApp = pos;
while (s.size() < Z) {
int v = gen(1,1000);
s.insert(v);
notApp.erase(v);
}
q[i] = toVec(s);
qSet[i] = s;
qR[i] = toVec(notApp);
qRSet[i] = notApp;
send(q[i]);
send(qR[i]);
}
auto r = wait();
for (int i = 0; i < T * 2; ++i) {
if (r[i] == false) {
if (i % 2 == 0) {
for (auto x : q[i / 2]) {
pos.erase(x);
}
} else if (i % 2 == 1) {
for (auto x : qR[i / 2]) {
pos.erase(x);
}
}
}
}
auto res3 = toVec(pos);
vector<int> res2(res3.size()), res1(res3.size());
vector<pii> copy(res3.size()), copy2(res3.size());
for (int i = 0; i < res3.size(); ++i) {
copy[i] = {gen(1,10000),res3[i]};
copy2[i] = {gen(1,10000),res3[i]};
}
std::sort(copy.begin(), copy.end());
std::sort(copy2.begin(), copy2.end());
for (int i = 0; i < res3.size(); ++i) {
res2[i] = copy[i].second;
res1[i] = copy2[i].second;
}
if (res3.size() == 2) return {res3[0],res3[1]};
if (res3.size() > 2) {
set<pii> newPos;
for (auto x : res2) {
for (auto y : res1) {
bool can = true;
for (int i = 0; i < T; ++i) {
int sum = r[i * 2] + r[i * 2 + 1];
if (sum == 2) {
if (qSet[i].count(x) && qSet[i].count(y)) can = false;
if (qRSet[i].count(x) && qRSet[i].count(y)) can = false;
}
}
if (!can) continue;
newPos.insert({min(x, y), max(x, y)});
}
}
return *newPos.begin();
}
if (res3.size() == 1) return {res3[0],res3[0]};
exit(5);
}
#if DEBUG
namespace sample_grader {
using std::cout;
using std::cin;
using std::endl;
using std::set;
using std::swap;
using std::vector;
constexpr int N = 1000;
struct Sample {
Sample()= default;
int R, H;
int r, h;
int a, b;
vector<int> answers;
[[noreturn]] void invalid_input() {
cout << "Invalid input" << endl;
exit(0);
}
[[noreturn]] void wrong_answer(const char *msg) {
cout << msg << endl;
exit(0);
}
void print_vector(vector<int> v) {
cout << "{";
for (size_t i = 0; i < v.size(); ++i) {
cout << v[i];
if (i + 1 != v.size()) cout << ", ";
}
cout << "}";
}
};
}
sample_grader::Sample s;
void send(std::vector<int> positions) {
using namespace sample_grader;
//cout << "send(";
//print_vector(positions);
//cout << ")" << endl;
++s.r;
if (s.r > s.R) s.wrong_answer("Out of robots");
set<int> position_set;
int curr_answer = 0;
for (int x: positions) {
if (x < 1 or x > N or position_set.find(x) != position_set.end()) {
s.wrong_answer("Invalid send");
}
position_set.insert(x);
if (x == s.a or x == s.b) curr_answer = 1;
}
s.answers.push_back(curr_answer);
}
std::vector<int> wait()
{
using namespace sample_grader;
s.h++;
//cout << "wait()";
//if (h <= H) {
// cout << " returns ";
// print_vector(answers);
//}
//cout << endl;
if (s.h > s.H) s.wrong_answer("Out of time");
vector<int> result = s.answers;
s.answers.clear();
return result;
}
int main()
{
srand(0);
int t = 0;
int corr = 0;
while (t < 10000) {
using namespace sample_grader;
s = Sample();
t++;
s.R = 70, s.H = 1;
s.a = rand() % 1000 + 1, s.b = rand()%1000 + 1;
if (s.a > s.b) swap(s.a, s.b);
auto p = scout(s.R, s.H);
//cout << "scout(" << s.R << ", " << s.H << ") returned {" << p.first << ", " << p.second << "}" << endl;
if (p.first > p.second) swap(p.first, p.second);
if (p.first == s.a and p.second == s.b) {
//cout << "Correct: " << s.r << " robot(s) used, " << s.h << " hour(s) passed" << endl;
corr++;
} else {
cout << "Wrong ans" << s.a << " " << s.b << endl;
}
}
cout << corr;
return 0;
}
#endif
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3888kb
input:
output:
result:
wrong answer Not correct
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 3ms
memory: 4212kb
input:
\x14
output:
result:
wrong answer Not correct
Subtask #3:
score: 0
Wrong Answer
Test #66:
score: 0
Wrong Answer
time: 4ms
memory: 4684kb
input:
\x1e
output:
result:
wrong answer Not correct
Subtask #4:
score: 0
Wrong Answer
Test #120:
score: 0
Wrong Answer
time: 131ms
memory: 4848kb
input:
K
output:
result:
wrong answer Not correct