Submission #988380

#	Time	Username	Problem	Language	Result	Execution time	Memory
988380		AlphaMale06	Xoractive (IZhO19_xoractive)	C++17	100 / 100	7 ms	600 KiB

Xoractive

#include <bits/stdc++.h>

//#include "interactive.h"

using namespace std;

int ask(int position);
vector<int> get_pairwise_xor(vector<int> positions);

vector<int> ers(vector<int> f, vector<int> s){
    vector<int> ret;
    int p = 0;
    for(int e : f){
        if(p<s.size() && s[p]==e){
            p++;
            continue;
        }
        ret.push_back(e);
    }
    return ret;
}

set<int> inter(set<int> a, set<int> b){
    set<int> ret;
    for(int e : a){
        if(b.find(e)!=b.end())ret.insert(e);
    }
    return ret;
}

vector<int> guess(int n) {
    vector<int> answer;
    set<int> vals;
    vector<int> queries[7];
    vector<int> answers[7];
    answer.resize(n);
    answer[0]=ask(1);
    if(n<=15){
        for(int i=2; i<=n; i++){
            answer[i-1]=ask(i);
        }
        return answer;
    }
    vector<int> q;
    for(int i=2; i<=n; i++){
        q.push_back(i);
    }
    for(int i=0; i< 7; i++){
        for(int j=2; j<=n; j++){
            if(!((j>>i)&1))queries[i].push_back(j);
        }
    }
    set<int> values[7];
    set<int> revals[7];
    for(int i=0; i< 7; i++){
        answers[i]=get_pairwise_xor(queries[i]);
        queries[i].push_back(1);
        answers[i]=ers(get_pairwise_xor(queries[i]), answers[i]);
        for(int j=1; j<answers[i].size(); j+=2)values[i].insert(answer[0]^answers[i][j]);
    }
    set<int> allvals;
    for(int i=0; i< 7; i++){
        for(int e : values[i])allvals.insert(e);
    }
    for(int i=0; i< 7; i++){
        for(int e : allvals){
            if(values[i].find(e)==values[i].end())revals[i].insert(e);
        }
    }
    for(int j=2; j<=n; j++){
        set<int> possible;
        for(int e : allvals)possible.insert(e);
        for(int i=0; i<7; i++){
            if(!((j>>i)&1)){
                possible = inter(possible, values[i]);
            }
            else possible = inter(possible, revals[i]);
        }
        answer[j-1] = (*possible.begin());
    }
    return answer;
}

Compilation message (stderr)

Xoractive.cpp: In function 'std::vector<int> ers(std::vector<int>, std::vector<int>)':
Xoractive.cpp:14:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         if(p<s.size() && s[p]==e){
      |            ~^~~~~~~~~
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int j=1; j<answers[i].size(); j+=2)values[i].insert(answer[0]^answers[i][j]);
      |                      ~^~~~~~~~~~~~~~~~~~

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