Submission #619264

#	Time	Username	Problem	Language	Result	Execution time	Memory
619264		juancarlovieri	Xoractive (IZhO19_xoractive)	C++17	100 / 100	6 ms	464 KiB

Xoractive

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

int uniq(vector<int> a, vector<int> b) {
	sort(b.begin(), b.end());
	for (auto i : a) {
		if (i == 0) continue;
		if (find(b.begin(), b.end(), i) != b.end()) return i;
	}
	assert(0);
}

vector<int> guess(int n) {
  vector<int> ans(n);
  ans[0] = ask(1);
  map<int, int> tmpans;
  for (int i = 0; i <= 7; ++i) {
    vector<int> tmp;
    for (int j = 2; j <= n; ++j) {
      if (j & (1 << i)) tmp.push_back(j);
    }
    if (tmp.empty()) break;

    tmp.push_back(1);
    // for (auto i : tmp) cout << i << ' ';
      // cout << endl;
    vector<int> res = get_pairwise_xor(tmp);
    multiset<int> all;
    for (auto i : res) all.insert(i);
      tmp.pop_back();
    res = get_pairwise_xor(tmp);
    for (auto i : res) all.erase(all.find(i));

    for (auto j : all) {
      if (j == 0) continue;
      tmpans[j ^ ans[0]]  |= (1 << i);
    }
  }

  for (auto i : tmpans) {
    ans[i.second - 1] = i.first;
  }
  // for (auto i : ans) cout << i << ' ';
  //   cout << endl;
  // int m = 15;
  // vector<bitset<100>> bm(m);
  // vector<pair<int, int>> ambil(n);
  // for (int i = 0; i < n - 1; ++i) {
  //   bool ada = 0;
  //   for (int j = 0; j < m; ++j) {
  //     for (int k = j + 1; k < m; ++k) {
  //       if ((bm[j] & bm[k]).count()) continue;
  //       ada = 1;
  //       ambil[i] = {j, k};
  //       bm[j].set(i);
  //       bm[k].set(i);
  //       break;
  //       // bm[j] |= (1 << i);
  //       // bm[k] |= (1 << i);
  //     }
  //     if (ada) break;
  //   }
  //   assert(ada);
  // }

  // for (int i = 0; i < n - 1; ++i) {

  // }

  // vector<vector<int>> res(m);
  // for (int i = 0; i < m; ++i) {
  // 	vector<int> tmp;
  // 	for (int j = 0; j < n; ++j) {
  // 		if (bm[i][j]) tmp.push_back(j + 1);
  // 	}
  // 	sort(tmp.begin(), tmp.end());
  // 	tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
  // 	// for (auto i : tmp) cout << i << ' ';
  // 	// 	cout << endl;
  // 	res[i] = get_pairwise_xor(tmp);
  // 	// for (auto j : res[i]) cout << j << ' ';
  // 	// cout << endl;
  // }

  // vector<int> ans(n);
  // ans[0] = ask(1);
  // for (int i = 0; i < n; ++i) {
  // 	// cout << ambil[i].first << ' ' << ambil[i].second << endl;
  // 	int tmp = uniq(res[ambil[i].first], res[ambil[i].second]);
  // 	// cout << tmp << endl;
  // 	ans[i + 1] = ans[i] ^ tmp;
  // }
  return ans;
}

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