Submission #257030

#	Time	Username	Problem	Language	Result	Execution time	Memory
257030		Kastanda	Xoractive (IZhO19_xoractive)	C++11	6 / 100	27 ms	1280 KiB

Xoractive

// M
#include<bits/stdc++.h>
#include "interactive.h"
using namespace std;
vector < int > RP;
mt19937 Rnd(time(0));
inline int Ask(int i)
{
        return (ask(RP[i]));
}
inline vector < int > GetSet(vector < int > A)
{
        for (int &a : A)
                a = RP[a];
        vector < int > Rs = get_pairwise_xor(A);
        /*printf("A is : ");
        for (int a : A)
                printf("%d ", a);
        printf("\n");
        printf("Rs is : ");
        for (int a : Rs)
                printf("%d ", a);
        printf("\n");*/
        for (int i = 0; i < (int)A.size(); i ++)
                assert(Rs[0] == 0), Rs.erase(Rs.begin());
        vector < int > Rs2;
        for (int i = 0; i < (int)Rs.size(); i += 2)
                Rs2.push_back(Rs[i]);
        /*printf("Rs2 is : ");
        for (int a : Rs2)
                printf("%d ", a);
        printf("\n");*/
        assert((int)Rs2.size() == (int)A.size() * ((int)A.size() - 1) / 2);
        return Rs2;
}
const int LG = 7;
set < int > All[LG];
multiset < int > ST[LG];
vector < int > vec[LG];
vector < int > guess(int n)
{
        RP.resize(n);
        iota(RP.begin(), RP.end(), 1);
        shuffle(RP.begin(), RP.end(), Rnd);

        int lg = LG;
        while ((1 << lg) >= n)
                lg --;
        lg ++;

        vector < int > Res(n, -1);
        Res[0] = Ask(0);
        for (int j = 0; j < lg; j ++)
                Res[1 << j] = Ask(1 << j);
        for (int j = 0; j < lg; j ++)
        {
                vec[j].clear();
                vec[j].push_back(0);
                for (int i = 1; i < n; i ++)
                        if (i >> j & 1)
                                vec[j].push_back(i);
                vec[j] = GetSet(vec[j]);
                ST[j].clear();
                for (int a : vec[j])
                        ST[j].insert(a);
                ST[j].erase(ST[j].lower_bound(Res[0] ^ Res[1 << j]));
                for (int a : ST[j])
                        if (ST[j].count(a ^ Res[0] ^ Res[1 << j]))
                                All[j].insert(a ^ Res[0]);
        }


        auto Try = [&](int i)
        {
                bool hs = 0;
                set < int > Nw;
                for (int j = 0; j < lg; j ++)
                        if (i >> j & 1)
                        {
                                if (hs == 0)
                                {
                                        hs = 1;
                                        for (int a : All[j])
                                                Nw.insert(a);
                                        continue;
                                }
                                set < int > Tobe;
                                for (int a : Nw)
                                        if (All[j].count(a))
                                                Tobe.insert(a);
                                Nw.swap(Tobe);
                                Tobe.clear();
                        }
                assert(Nw.size());
                if (Nw.size() > 1)
                        return 0;
                Res[i] = * Nw.begin();
                return 1;
        };

        auto Del = [&](int i)
        {
                for (int j = 0; j < lg; j ++)
                        if (i >> j & 1)
                        {
                                for (int h = 0; h < n; h ++)
                                        if (i != h && Res[h] != -1 && (h == 0 || (h >> j & 1)))
                                                ST[j].erase(ST[j].lower_bound(Res[i] ^ Res[h]));
                                All[j].clear();
                                for (int a : ST[j])
                                        if (ST[j].count(a ^ Res[0] ^ Res[1 << j]))
                                                All[j].insert(a ^ Res[0]);
                        }
                return ;
        };

        while (true)
        {
                bool Fail = 1;
                for (int i = 0; i < n; i ++)
                        if (Res[i] == -1 && Try(i))
                                Fail = 0, Del(i);
                if (Fail) break;
        }
        for (int i = 0; i < n; i ++)
                assert(Res[i] != -1);
        vector < int > Rs(n);
        for (int i = 0; i < n; i ++)
                Rs[RP[i] - 1] = Res[i];
        return Rs;
}

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