Submission #257492

#	Time	Username	Problem	Language	Result	Execution time	Memory
257492		BThero	Xoractive (IZhO19_xoractive)	C++17	88 / 100	101 ms	672 KiB

Xoractive

// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
#include "interactive.h"

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

int n;
vi arr;

void print(vi x) {
  fprintf(stderr, "%d:", x.size());
  
  for (int y : x) {
    fprintf(stderr, " %d", y);
  }
  
  fprintf(stderr, "\n");
}

int query(int x) {
  return ask(x + 1);
}

vi query(vi x) {
  for (int &y : x) {
    ++y;
  }
  
  return get_pairwise_xor(x);
}

vi subt(vi a, vi b) {
  for (int x : b) {
    a.erase(find(all(a), x));
  }
  
  return a;
}

vi getSet(vi a) {
  vi b = a;
  b.pb(n);
  a = query(a);
  b = query(b);
  b = subt(b, a);
  b.erase(find(all(b), 0));
  b.resize(unique(all(b)) - b.begin());
  
  for (int &x : b) {
    x ^= arr[n];
  }
  
  sort(all(b));
  return b;
}

vi guess(int _n) {
  n = _n;
  arr = vi(n);
  
  if (n <= 10) {
    for (int i = 0; i < n; ++i) {
      arr[i] = query(i);
    }
    
    return arr;
  }
  
  arr[n - 1] = query(n - 1);
  --n;
  
  int step = 1;
  
  while (step < n) { 
    step *= 2;
  }
  
  vi A, B;
  vvi S;
  
  for (int i = 0; i < n; ++i) {
    if (i % step < step / 2) {
      A.pb(i);
    }
    else {
      B.pb(i);
    }
  }
  
  S.pb(getSet(A));
  S.pb(getSet(B));
  step /= 2;
  
  while (step > 1) {
    A.clear();
    
    for (int j = 0; j < n; ++j) {
      if (j % step < step / 2) {
        A.pb(j);
      } 
    }
    
    A = getSet(A);
    int m = (int)S.size();
    vvi buckets(m), newS;
    
    for (int x : A) {
      for (int i = 0; i < m; ++i) {
        if (find(all(S[i]), x) != S[i].end()) {
          buckets[i].pb(x);
        }
      }
    }
    
    for (int i = 0; i < m; ++i) {
      vi A = buckets[i];
      vi B = subt(S[i], A);
      
      if (!A.empty()) {
        newS.pb(A);
      }
      
      if (!B.empty()) {
        newS.pb(B);
      }
    }
    
    S = newS;
    step /= 2;
  }
  
  assert((int)S.size() == n);
  
  for (int i = 0; i < n; ++i) {
    assert((int)S[i].size() == 1);
    arr[i] = S[i][0];
  }
  
  return arr;
}

Compilation message (stderr)

Xoractive.cpp: In function 'void print(vi)':
Xoractive.cpp:24:34: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   fprintf(stderr, "%d:", x.size());
                          ~~~~~~~~^

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