Submission #146191

#	Time	Username	Problem	Language	Result	Execution time	Memory
146191		imeimi2000	Xoractive (IZhO19_xoractive)	C++17	100 / 100	12 ms	632 KiB

Xoractive

#include "interactive.h"
#include <vector>
#include <set>

using namespace std;

multiset<int> query(vector<int> pos) {
    multiset<int> sp;
    if (pos.empty()) return sp;
    for (int i : get_pairwise_xor(pos)) sp.insert(i);
    return sp;
}

vector<int> guess(int n) {
    vector<int> ret;
    ret.push_back(ask(1));
    set<int> in[7];
    set<int> all;
    for (int i = 0; i < 7; ++i) {
        vector<int> B;
        for (int j = 2; j <= n; ++j) {
            if (((j >> i) & 1) == 0) continue;
            B.push_back(j);
        }
        multiset<int> sp2 = query(B);
        B.push_back(1);
        multiset<int> sp1 = query(B);
        sp1.erase(sp1.find(0));
        for (int j : sp2) sp1.erase(sp1.find(j));
        for (int j : sp1) {
            in[i].insert(j ^= ret[0]);
            all.insert(j);
        }
    }
    for (int i = 2; i <= n; ++i) {
        set<int> sp = all;
        for (int j = 0; j < 7; ++j) {
            if (((i >> j) & 1) == 0) continue;
            set<int> nxt;
            for (int k : in[j]) {
                auto it = sp.find(k);
                if (it == sp.end()) continue;
                nxt.insert(k);
            }
            sp = nxt;
        }
        for (int j = 0; j < 7; ++j) {
            if ((i >> j) & 1) continue;
            for (int k : in[j]) {
                auto it = sp.find(k);
                if (it == sp.end()) continue;
                sp.erase(it);
            }
        }
        ret.push_back(*sp.begin());
    }
    return ret;
}

• Subtask 1: 6 / 6
• Subtask 2: 94 / 94