Submission #376853

#	Time	Username	Problem	Language	Result	Execution time	Memory
376853		ijxjdjd	Xoractive (IZhO19_xoractive)	C++14	88 / 100	19 ms	640 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;

int first = -1;
vector<int> getNums(vector<int> a) {
    vector<int> q(a.size()+1);
    for (int i = 0; i < a.size(); i++) {
        q[i] = a[i]+1;
    }
    q[a.size()] = 1;
    vector<int> tot = get_pairwise_xor(q);
    q.resize(a.size());

    vector<int> own = get_pairwise_xor(q);
    vector<int> res(2*a.size()+1);
    set_difference(all(tot), all(own), res.begin());
    sort(res.begin(), res.end());
    res.resize(unique(res.begin(), res.end())-res.begin());
    assert(res.size() == a.size()+1 && res[0] == 0);
    vector<int> ret(a.size());
    for (int i = 1; i < res.size(); i++) {
        ret[i-1] = res[i]^first;
    }
    sort(all(ret));
    return ret;
}
vector<int> guess(int n) {
	vector <int> ans(n);
//	if (n <= 15) {
//        for (int i = 0; i < n; i++) {
//            ans[i] = ask(i+1);
//        }
//        return ans;
//	}

	first = ask(1);
	ans[0] = first;
	vector<int> av(n-1);
	for (int i = 1; i < n; i++) {
        av[i-1] = i;
	}
	vector<int> tot = getNums(av);
    vector<vector<int>> on(7);
    vector<vector<int>> off(7, vector<int>(n));
    for (int i = 0; i < 7; i++) {
        vector<int> prep;
        for (int j = 0; j < n; j++) {
            if ((1<<i)&j) {
                prep.push_back(j);
            }
        }
        if (prep.size() != 0) {
            on[i] = getNums(prep);
        }
        off[i].resize(set_difference(all(tot), all(on[i]), off[i].begin())-off[i].begin());
    }
    for (int i = 1; i < n; i++) {
        vector<int> cur(tot.size());
        copy(all(tot), cur.begin());
        for (int b = 0; b < 7; b++) {
            vector<int>& nxt = (((1<<b)&i) ? on[b] : off[b]);
            cur.resize(set_intersection(all(cur), all(nxt), cur.begin())-cur.begin());
        }
        assert(cur.size() == 1);
        ans[i] = cur[0];
    }
	return ans;
}

Compilation message (stderr)

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

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