Submission #687661

#	Time	Username	Problem	Language	Result	Execution time	Memory
687661		Matteo_Verz	Xoractive (IZhO19_xoractive)	C++17	0 / 100	3063 ms	208 KiB

Xoractive

#include <bits/stdc++.h>
#include "interactive.h"
#ifdef BLAT
    #include "debug/debug.hpp"
#else
    #define debug(x...)
#endif

using namespace std;

void remove_junk(vector <int> &v) {
    vector <int> v2;
    for (int i = 0; i < v.size(); i += 2)
        if (v[i] != 0)
            v2.push_back(v[i]);
    v = v2;
}

int first, offset;
vector <int> ans;
void check(const vector <int> &q, int chosen) {
    debug(q, chosen);
    vector <int> v, others;
    for (int i = 0; i < q.size(); i++) {
        if (chosen & (1 << i))
            v.push_back(q[i] ^ first);
        else others.push_back(q[i]);
    }

    debug(v, others);
    vector <int> pattern;
    for (int i = 0; i < v.size(); i++)
        for (int j = i + 1; j < v.size(); j++)
            pattern.push_back(v[i] ^ v[j]);
    
    sort(pattern.begin(), pattern.end());
    debug(pattern);

    if (pattern == others)
        for (int i = 0; i < v.size(); i++)
            ans[offset + i] = v[i] ^ first;
}

void backtrack(const vector <int> &q, int chosen, int pos = 0) {
    int n = q.size();
    if (pos == n) {
        if (__builtin_popcount(chosen) == (n + 1) / 2)
            check(q, chosen);

        return;
    }

    if (__builtin_popcount(chosen) < (n + 1) / 2)
        backtrack(q, chosen ^ (1 << pos), pos + 1);
    backtrack(q, chosen, pos + 1);
}

vector <int> guess(int n) {
    vector <int> asks;
    ans.resize(n);
    ans[0] = first = ask(1);
    for (int i = 2; i <= n; i += 7) {
        asks.clear(); asks.push_back(1);
        for (int j = i; j < i + 7 && j <= n; j++)
            asks.push_back(j);
        
        debug(asks);
        auto q = get_pairwise_xor(asks);
        remove_junk(q);
        debug(q);

        int chosen = 0;
        offset = i - 1;
        if (q.size() == asks.size() * (asks.size() - 1) / 2)
            backtrack(q, chosen);

        /*for (auto it : q)
            cerr << it << ' ';
        cerr << '\n';*/
    }

    return ans;
}

Compilation message (stderr)

Xoractive.cpp: In function 'void remove_junk(std::vector<int>&)':
Xoractive.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < v.size(); i += 2)
      |                     ~~^~~~~~~~~~
Xoractive.cpp: In function 'void check(const std::vector<int>&, int)':
Xoractive.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i < q.size(); i++) {
      |                     ~~^~~~~~~~~~
Xoractive.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
Xoractive.cpp:33:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int j = i + 1; j < v.size(); j++)
      |                             ~~^~~~~~~~~~
Xoractive.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i < v.size(); i++)
      |                         ~~^~~~~~~~~~

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