제출 #396486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
396486		rama_pang	Xoractive (IZhO19_xoractive)	C++17	100 / 100	9 ms	456 KiB

Xoractive

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

vector<int> guess(int n) {
  vector<int> ans;
  ans.emplace_back(ask(1));
  vector<vector<int>> ls(7); // ls[b] = list of numbers in positions where the b-th bit is ON.
  for (int b = 0; b < 7; b++) {
    vector<int> x;
    for (int pos = 1; pos < n; pos++) {
      if ((pos >> b) & 1) {
        x.emplace_back(pos + 1);
      }
    }
    if (x.empty()) {
      ls[b].emplace_back(-1);
      continue;
    }
    auto del = get_pairwise_xor(x);
    x.emplace_back(1);
    ls[b] = get_pairwise_xor(x);
    ls[b].erase(find(begin(ls[b]), end(ls[b]), 0)); // delete A[0] ^ A[0]
    for (auto &j : del) {
      ls[b].erase(find(begin(ls[b]), end(ls[b]), j));
    }
    for (auto &j : ls[b]) { // A[0] ^ A[pos]
      j ^= ans[0]; // turn to A[pos]
    }
  }

  for (int pos = 1; pos < n; pos++) {
    vector<int> candidate;
    for (int b = 0; b < 7; b++) if (ls[b][0] != -1) {
      if ((pos >> b) & 1) { // element must be in this list
        if (candidate.empty()) {
          candidate = ls[b];
        } else {
          vector<int> newcand;
          for (auto i : ls[b]) {
            if (count(begin(candidate), end(candidate), i)) {
              newcand.emplace_back(i);
            }
          }
          candidate = newcand;
        }
      }
    }

    assert(!candidate.empty());
    for (int b = 0; b < 7; b++) if (ls[b][0] != -1) {
      if (!((pos >> b) & 1)) { // element must not be in this list
        for (auto i : ls[b]) {
          if (count(begin(candidate), end(candidate), i)) {
            candidate.erase(find(begin(candidate), end(candidate), i));
          }
        }
      }
    }

    ans.emplace_back(candidate[0]);
  }

  return ans;
}

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