QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#428780#7281. How to Avoid Disqualification in 75 Easy StepsCrafticat0 2ms5068kbC++145.8kb2024-06-01 21:40:442024-06-01 21:40:44

Judging History

你现在查看的是最新测评结果

  • [2024-06-01 21:40:44]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:5068kb
  • [2024-06-01 21:40:44]
  • 提交

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 = 25;
    srand(time(nullptr));

    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);
    int mul = 500;
    for (int i = 0; i < T; ++i) {
        set<int> s;
        set<int> notApp;
        int mine = mul;
        mul /= 2;
        if (mul > 0) {
            int org = mine;
            bool t = true;
            for (int j = 1; j <= 1000; ++j) {
                if (t) s.insert(j);
                else
                    notApp.insert(j);
                if (--mine <= 0) {
                    mine = org;
                    t = !t;
                }
            }
        } else {
            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: 1ms
memory: 4100kb

input:



output:


result:

wrong answer Not correct

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 2ms
memory: 4396kb

input:

\x14

output:


result:

wrong answer Not correct

Subtask #3:

score: 0
Wrong Answer

Test #66:

score: 0
Wrong Answer
time: 0ms
memory: 4772kb

input:

\x1e

output:


result:

wrong answer Not correct

Subtask #4:

score: 0
Wrong Answer

Test #120:

score: 0
Wrong Answer
time: 2ms
memory: 5068kb

input:

K

output:


result:

wrong answer Not correct