QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#350326#8216. Jumbled Primesucup-team1198#AC ✓853ms3880kbC++206.0kb2024-03-10 17:16:512024-03-10 17:16:51

Judging History

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

  • [2024-03-10 17:16:51]
  • 评测
  • 测评结果:AC
  • 用时:853ms
  • 内存:3880kb
  • [2024-03-10 17:16:51]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int ask_count = 0;
vector<int> ans_p;

int gcd(int x, int y) {
    if (x == 0) return y;
    return gcd(y % x, x);
}

map<pair<int, int>, int> mem;

int ask(int p1, int p2) {
    // mem?

    if (mem.count({p1, p2})) return mem[{p1, p2}];
    if (mem.count({p2, p1})) return mem[{p2, p1}];

    ++ask_count;

    // mem[{p1, p2}] = gcd(ans_p[p1], ans_p[p2]);
    // return gcd(ans_p[p1], ans_p[p2]);

    cout << "? " << p1 + 1 << ' ' << p2 + 1 << endl;
    int res;
    cin >> res;

    mem[{p1, p2}] = res;

    return res;
}

string answer;

bool prime(int x) {
    // if (x == 1) return 1;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) return 0;
    }
    return 1;
}

void check() {
    for (int i = 0; i < 100; ++i) {
        if (answer[i] - '0' != prime(ans_p[i])) {
            cerr << "wrong! " << i + 1 << '\n';
            assert(0);
        }
    }
}

vector<vector<int>> sep(vector<int> ind, int with, vector<int> by, int mark = 0) {
    vector<vector<int>> res(by.size() + 1);
    for (int i : ind) {
        if (i == with) {
            if (mark >= 1) {
                answer[i] = '0';
            }
            res[0].push_back(i);
            continue;
        }
        int a = ask(i, with);
        for (int j = 0; j <= by.size(); ++j) {
            if (j == by.size() || gcd(a, by[j]) % by[j] == 0) {

                if (j < mark) {
                    // cerr << "mark " << i + 1 << '\n';
                    answer[i] = '0';
                }

                res[j].push_back(i);
                break;
            }
        }
    }
    return res;
}

int fnd(vector<int> ind, int by) {
    int p1 = -1;
    int p2 = -1;
    while (true) {
        p1 = ind[rand() % ind.size()];
        p2 = p1;
        while (p2 == p1) p2 = ind[rand() % ind.size()];

        if (ask(p1, p2) % by == 0) break;
    }
    return p1;  // forget p2
}

vector<pair<int, int>> big_primes(vector<int> ind, vector<int> indp) {
    vector<pair<int, int>> res;
    for (int i : indp) {
        for (int j = 0; j < ind.size(); ++j) {
            int a = ask(i, ind[j]);
            if (a != 1) {
                res.push_back({i, a});
                answer[ind[j]] = '0';
                ind.erase(ind.begin() + j);
                break;
            }
        }
    }
    return res; // ind, val
}

void filter(vector<int> ind, int d, vector<pair<int, int>> bp) {
    for (auto p : bp) {
        if (p.second * d > 100) continue;
        for (int i = 0; i < ind.size(); ++i) {
            int a = ask(ind[i], p.first);
            if (a != 1) {
                answer[ind[i]] = '0';
                ind.erase(ind.begin() + i);
                break;
            }
        }
    }
}

void find_p2(vector<int> ind, vector<int> with, int g) {
    bool checked = false;
    for (int i : ind) {
        if (answer[i] == '0') continue;
        if (checked) {
            answer[i] = '0';
            break;
        }
        
        for (int j : with) {
            if (ask(i, j) % g == 0) {
                checked = true;
                break;
            }
        }

        if (checked) {
            answer[i] = '0';
            break;
        }

        checked = true;
    }
}

void print(vector<int> v, string name = "vec") {
    cerr << name << " = ";
    for (int i : v) {
        cerr << i + 1 << ' ';
    }
    cerr << '\n';
}

void print(vector<vector<int>> v, string name = "vec") {
    cerr << name << " = ";
    for (auto vv : v) {
        for (auto i : vv) {
            cerr << i + 1 << ' ';
        }
        cerr << '\n';
    }
    cerr << '\n';
}


void solve() {
    int n = 100;
    answer.assign(n, '1');

    vector<int> ind(n);
    iota(ind.begin(), ind.end(), 0);
    // rsh

    int d4 = fnd(ind, 4);
    vector<vector<int>> d421 = sep(ind, d4, {4, 2}, 1);
    // print(d421, "d421");

    int d9 = fnd(d421[2], 9);
    vector<vector<int>> d931 = sep(d421[2], d9, {9, 3}, 1);
    // print(d931, "d931");

    int d5 = fnd(d931[2], 5);
    vector<vector<int>> d51 = sep(d931[2], d5, {5});
    // print(d51, "d51");


    int d7 = fnd(d51[1], 7);
    vector<vector<int>> d71 = sep(d51[1], d7, {7});

    // print(d51, "d71");


    vector<int> p1_11 = d71[1];

    vector<vector<int>> c_35_ost = sep(d51[0], d71[0][0], {7}, 1);

    vector<vector<int>> c_3_57_ost = sep(d931[1], c_35_ost[0][0], {5, 7}, 2);
    vector<vector<int>> c_2_57_ost = sep(d421[1], c_35_ost[0][0], {5, 7}, 2);
    vector<vector<int>> c_2_357_ost = sep(c_2_57_ost[2], d931[0][0], {3}, 1);  // mb long

    // left only c_35_ost[1] (5, 25, no35, 55, 65 ...), d71[0] (7, 49, 77, 91), c_2_357_ost[1], c_3_57_ost[2]

    vector<pair<int, int>> bp = big_primes(c_2_357_ost[1], p1_11);
    filter(c_3_57_ost[2], 3, bp);
    filter(d71[0], 7, bp);
    filter(c_35_ost[1], 5, bp);

    // ost 5, 25 & 7, 49

    // print(c_35_ost[1], "c_35_ost[1]");
    // print(c_2_57_ost[0], "c_2_57_ost[0]");
    // print(d71[0], "d71[0]");
    // print(c_2_57_ost[1], "c_2_57_ost[1]");

    find_p2(c_35_ost[1], c_2_57_ost[0], 25);
    find_p2(d71[0], c_2_57_ost[1], 49);

    // check();

    cout << "! " << answer << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // ans_p.resize(100);
    // iota(ans_p.begin(), ans_p.end(), 1);

    for (int t = 0; t < 1000; ++t) {
        mem.clear();
        // random_shuffle(ans_p.begin(), ans_p.end());
        // random_shuffle(ans_p.begin(), ans_p.end());
        solve();
    }

    // cerr << ask_count << '\n';

    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 853ms
memory: 3880kb

input:

1
1
1
3
1
1
1
3
1
2
1
1
3
1
1
1
1
1
2
4
1
1
1
1
1
2
2
1
1
1
2
2
1
2
1
4
4
4
16
4
1
1
1
2
8
1
1
1
1
1
1
1
1
8
1
2
8
2
1
1
1
16
2
1
2
2
4
1
1
1
2
1
1
1
2
2
4
1
4
1
1
16
4
4
1
1
2
8
2
2
16
8
1
2
1
1
1
2
1
16
1
2
4
1
2
2
8
1
1
2
2
1
4
1
1
4
2
1
3
31
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
1
1
1
1
...

output:

? 84 87
? 78 16
? 94 36
? 87 93
? 50 22
? 63 28
? 91 60
? 64 27
? 41 27
? 73 37
? 12 69
? 68 30
? 83 31
? 63 24
? 68 36
? 30 3
? 23 59
? 70 68
? 94 57
? 12 43
? 1 12
? 2 12
? 3 12
? 4 12
? 5 12
? 6 12
? 7 12
? 8 12
? 9 12
? 10 12
? 11 12
? 13 12
? 14 12
? 15 12
? 16 12
? 17 12
? 18 12
? 19 12
? 20 1...

result:

ok Primes are found successfully with S = 551263 queries total