제출 #227751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
227751		emil_physmath	Xoractive (IZhO19_xoractive)	C++17	100 / 100	8 ms	560 KiB

Xoractive

#include <algorithm>
#include "interactive.h"
#include <vector>
#include <map>
#include <set>
#include <iostream>
using namespace std;
using llong = long long;

set<int> atbit[100];

vector<int> guess(int n)
{
    vector<int> res(n + 1);
    res[1] = ask(1);
    set<int> anses;
    for (int bit = 0; (1 << bit) <= n; ++bit)
    {
        vector<int> ind;
        for (int i = 2; i <= n; ++i)
            if (i & (1 << bit))
                ind.push_back(i);
        if (ind.empty()) continue;
        vector<int> b = get_pairwise_xor(ind);
        sort(b.begin(), b.end());
        ind.push_back(1);
        vector<int> a = get_pairwise_xor(ind);
        sort(a.begin(), a.end());
        vector<int> x;
        set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(x));
        for (int& y: x)
            y ^= res[1];
        atbit[bit].insert(x.begin(), x.end());
        atbit[bit].erase(res[1]);
        anses.insert(x.begin(), x.end());
    }
    anses.erase(res[1]);
    for (int i = 2; i <= n; ++i)
        for (int ans: anses)
        {
            bool f = true;
            for (int bit = 0; (1 << bit) <= n; ++bit)
            {
                bool g = (i & (1 << bit));
                if (atbit[bit].count(ans) != g)
                {
                    f = false;
                    break;
                }
            }
            if (f)
            {
                res[i] = ans;
                break;
            }
        }
    res.erase(res.begin());
    return res;
}

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