Submission #958088

#	Time	Username	Problem	Language	Result	Execution time	Memory
958088		shmax	Xoractive (IZhO19_xoractive)	C++17	100 / 100	4 ms	596 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>

using namespace std;

template<typename T>
using vec = vector<T>;
#define bit(x, i) ((x >> i) & 1)

vector<int> guess(int n) {
    vector<int> ans(n);
    ans[0] = ask(1);
    map<int, int> ans_map;
    ans_map[ans[0]] = 0;
    for (int b = 10; b >= 0; b--) {
        vec<int> ids;
        for (int i = 1; i < n; i++)
            if (bit(i, b)) ids.push_back(i + 1);
        if (ids.empty()) continue;
        auto xors1 = get_pairwise_xor(ids);
        ids.push_back(1);
        auto xors2 = get_pairwise_xor(ids);
//        find diff
        multiset<int> xors1_ms(xors1.begin(), xors1.end());
        vec<int> diff;
        for (int i: xors2) {
            if (xors1_ms.count(i) == 0) {
                diff.push_back(i);
            } else {
                xors1_ms.erase(xors1_ms.find(i));
            }
        }
        sort(diff.begin(), diff.end());
//        unique(diff.begin(), diff.end());
        diff.erase(unique(diff.begin(), diff.end()), diff.end());
        for (int i = 1; i < diff.size(); i++) {
            int vl = diff[i] ^ ans[0];
            if (ans_map.count(vl) == 0) {
                ans_map[vl] = 0;
            }
            ans_map[vl] += 1 << b;
        }
    }
    for (auto &p: ans_map) {
        ans[p.second] = p.first;
    }
    return ans;
}

Compilation message (stderr)

Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 1; i < diff.size(); i++) {
      |                         ~~^~~~~~~~~~~~~

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