Submission #370890

#	Time	Username	Problem	Language	Result	Execution time	Memory
370890		daniel920712	Xoractive (IZhO19_xoractive)	C++14	88 / 100	15 ms	876 KiB

Xoractive

#include "interactive.h"
#include <stdio.h>
#include <vector>
#include <set>
#include <map>

using namespace std;
set < int > all;
map < int , int > A;
map < int , int > B;
set < int > AA;
set < int > BB;
set < int > bit[15][15];
vector < int > how;
vector < int > ans;
vector < int > tt;
vector < int > tt2;
void F()
{
    int i,j;
    ans[0]=ask(1);

    A.clear();
    B.clear();
    tt.clear();
    for(auto i:how)
    {
        //printf("%d\n",i);
        tt.push_back(i+1);
    }
    tt2=get_pairwise_xor(tt);
    for(auto i:tt2) if(i) A[i]++;

    tt.clear();
    for(auto i:how) if(i) tt.push_back(i+1);
    tt2=get_pairwise_xor(tt);
    for(auto i:tt2) if(i) A[i]--;

    all.insert(ans[0]);
    for(auto i:A)
    {
        for(j=0;j<i.second/2;j++) all.insert(i.first^ans[0]);
    }

    /*printf("aaa\n");
    for(auto i:all) printf("%d ",i);
    printf("\n");*/
}

void F2(int here)
{

    int i,j;
    A.clear();
    B.clear();
    tt.clear();
    for(auto i:how)
    {
        //printf("%d\n",i);
        tt.push_back(i+1);
    }
    tt2=get_pairwise_xor(tt);
    for(auto i:tt2) if(i) A[i]++;

    tt.clear();
    for(auto i:how) if(i) tt.push_back(i+1);
    tt2=get_pairwise_xor(tt);
    for(auto i:tt2) if(i) A[i]--;

    bit[0][here].insert(ans[0]);
    for(auto i:A)
    {
        for(j=0;j<i.second/2;j++) bit[0][here].insert(i.first^ans[0]);
    }

    /*printf("aa\n");
    for(auto i:bit[0][here]) printf("%d ",i);
    printf("\n");*/
    //printf("\n");
}
vector<int> guess(int N)
{
    //BB
    int i,j,big=0;
	for(i=0;i<N;i++) ans.push_back(0);


    if(N<=2)
    {
        for(i=0;i<N;i++) ans[i]=ask(i+1);
        return ans;
    }
    else
    {
        for(i=0;i<N;i++) how.push_back(i);
        F();
        for(i=0;i<10;i++)
        {
            how.clear();
            //printf("bb %d\n",i);
            for(j=0;j<N;j++)
            {
                if((j&(1<<i))==0)
                {
                    //printf("%d ",j);
                    how.push_back(j);
                }
            }
            //printf("\n");
            if(how.size()==N||how.size()==0)
            {
                big=i;
                break;
            }
            F2(i);
            for(auto j:all) if(bit[0][i].find(j)==bit[0][i].end()) bit[1][i].insert(j);
        }

        for(i=0;i<N;i++)
        {
            AA.clear();
            for(auto j:all) AA.insert(j);
            for(j=0;j<big;j++)
            {
                if((i&(1<<j))==0)
                {
                    BB.clear();
                    for(auto k:AA) if(bit[0][j].find(k)==bit[0][j].end()) BB.insert(k);
                    for(auto k:BB) AA.erase(k);
                }
                else
                {
                    BB.clear();
                    for(auto k:AA) if(bit[1][j].find(k)==bit[1][j].end()) BB.insert(k);
                    for(auto k:BB) AA.erase(k);
                }
            }
            ans[i]=*AA.begin();
        }
    }


	return ans;
}

Compilation message (stderr)

Xoractive.cpp: In function 'void F()':
Xoractive.cpp:20:9: warning: unused variable 'i' [-Wunused-variable]
   20 |     int i,j;
      |         ^
Xoractive.cpp: In function 'void F2(int)':
Xoractive.cpp:53:9: warning: unused variable 'i' [-Wunused-variable]
   53 |     int i,j;
      |         ^
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:110:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |             if(how.size()==N||how.size()==0)
      |                ~~~~~~~~~~^~~

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