제출 #241963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241963		valerikk	Xoractive (IZhO19_xoractive)	C++17	100 / 100	11 ms	512 KiB

Xoractive

#include "interactive.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
//#define int ll

#define mp make_pair
#define pb push_back
#define x first
#define y second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

vector<int> get_xor(vector<int> pos) {
  if (pos.empty()) return {};
  for (auto &i : pos) i++;
  auto kek = get_pairwise_xor(pos);
  map<int, int> cnt;
  for (auto i : kek) {
    if (i != 0) cnt[i]++;
  }
  vector<int> flex;
  for (auto i : cnt) {
    i.y /= 2;
    while (i.y--) {
      flex.pb(i.x);
    }
  }
  return flex;
}

vector<int> get_kek(int a1, vector<int> pos) {
  auto kek1 = get_xor(pos);
  pos.pb(0);
  auto kek2 = get_xor(pos);
  map<int, int> cnt;
  for (auto i : kek2) cnt[i]++;
  for (auto i : kek1) cnt[i]--;
  vector<int> res;
  for (auto i : cnt) {
    if (i.y) {
      res.pb(i.x ^ a1);
    }
  }
  return res;
}

vector<int> guess(int n) {
  vector<int> a(n);
  a[0] = ask(1);
  set<int> st;
  vector<set<int>> have(7);
  for (int i = 0; i < 7; i++) {
    vector<int> pos;
    for (int j = 1; j < n; j++) {
      if ((j >> i) & 1) pos.pb(j);
    }
    auto kek = get_kek(a[0], pos);
    for (auto flex : kek) {
      st.insert(flex);
      have[i].insert(flex);
    }
  }
  for (auto i : st) {
    int ind = 0;
    for (int j = 0; j < 7; j++) {
      if (have[j].count(i)) ind += 1 << j;
    }
    a[ind] = i;
  }
  return a;
}

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