Submission #370529

#	Time	Username	Problem	Language	Result	Execution time	Memory
370529		casperwang	Xoractive (IZhO19_xoractive)	C++14	Compilation error	0 ms	0 KiB

Xoractive

#include "interactive.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 100;

vector<int> guess(int n) {
	vector <int> G;
  vector <int> ans(n);
  if (n <= 50) {
    for (int i = 1; i <= n; i++)
      ans[i-1] = ask(i);
    return ans;
  }

  for (int i = 2; i <= n; i++)
    G.pb(i);
  vector <int> exp = get_pairwise_xor(G);
  G.pb(1);
  vector <int> all = get_pairwise_xor(G);

  set <int> nums;
  vector <int> arr, pos(n);
  ans[0] = ask(1);
  int j = 0;
  for (int i = 0; i < exp.size(); i++, j++)
    while (all[j] != exp[i])
      nums.insert(all[j++] ^ ans[0]);
  while (j < all.size()) nums.insert(all[j++] ^ ans[0]);
  for (int i : nums) arr.pb(i);
  srand(time(NULL));
  random_shuffle(arr.begin(), arr.end());

  for (int i = 0; (1<<i) < n; i++) {
    G.clear();
    for (int j = 0; j < n; j++)
      if (!(j&(1<<i))) G.pb(j+1);
    vector <int> res = get_pairwise_xor(G);
    vector <int> tmp, nxt;
    for (int j = 0; j < n; j++) tmp.pb(j);
    while (tmp.size() > G.size()) {
      for (int j : tmp) {
        int cnt = 0;
        for (int k : tmp) {
          int val = arr[j] ^ arr[k];
          if (res[res.size()-1] >= val && *lower_bound(res.begin(), res.end(), val) == val)
            cnt++;
        }
        if (cnt >= G.size()) nxt.pb(j);
      }
      if (tmp.size() == nxt.size()) break;
      tmp = nxt;
      nxt.clear();
    }
    vector <int> path[MAXN];
    for (int j = 0; j < n; j++) path[j].clear();
    for (int j : tmp) {
      int cnt = 0;
      for (int k : tmp) {
        int val = arr[j] ^ arr[k];
        if (res[res.size()-1] >= val && *lower_bound(res.begin(), res.end(), val) == val)
          if (j != k) path[j].pb(k);
      }
    }
    sort(tmp.begin(), tmp.end(), [](const int a, const int b) {
        return path[a].size() < path[b].size();
    });
    for (int j : tmp) {
      bool flag = true;
      set <int> appr;
      for (int k : path[j]) appr.insert(k);
      appr.insert(j);
      for (int k : path[j]) {
        int c = 0;
        for (int p : path[k]) {
          if (appr.count(p)) c++;
        }
        if (c != G.size()-1) flag = false;
      }
      if (flag) {
        tmp = path[j];
        tmp.pb(j);
        break;
      }
    }
    for (int j = 0; j < n; j++) pos[j] += (1<<i);
    for (int j : tmp) pos[j] -= (1<<i);
  }
  for (int i = 0; i < n; i++)
    ans[pos[i]] = arr[i];
	return ans;
}

Compilation message (stderr)

Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (int i = 0; i < exp.size(); i++, j++)
      |                   ~~^~~~~~~~~~~~
Xoractive.cpp:34:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   while (j < all.size()) nums.insert(all[j++] ^ ans[0]);
      |          ~~^~~~~~~~~~~~
Xoractive.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if (cnt >= G.size()) nxt.pb(j);
      |             ~~~~^~~~~~~~~~~
Xoractive.cpp:63:11: warning: unused variable 'cnt' [-Wunused-variable]
   63 |       int cnt = 0;
      |           ^~~
Xoractive.cpp: In lambda function:
Xoractive.cpp:71:16: error: 'path' is not captured
   71 |         return path[a].size() < path[b].size();
      |                ^~~~
Xoractive.cpp:70:35: note: the lambda has no capture-default
   70 |     sort(tmp.begin(), tmp.end(), [](const int a, const int b) {
      |                                   ^
Xoractive.cpp:60:18: note: 'std::vector<int> path [100]' declared here
   60 |     vector <int> path[MAXN];
      |                  ^~~~
Xoractive.cpp:71:33: error: 'path' is not captured
   71 |         return path[a].size() < path[b].size();
      |                                 ^~~~
Xoractive.cpp:70:35: note: the lambda has no capture-default
   70 |     sort(tmp.begin(), tmp.end(), [](const int a, const int b) {
      |                                   ^
Xoractive.cpp:60:18: note: 'std::vector<int> path [100]' declared here
   60 |     vector <int> path[MAXN];
      |                  ^~~~
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:83:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         if (c != G.size()-1) flag = false;
      |             ~~^~~~~~~~~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:71,
                 from /usr/include/c++/9/vector:60,
                 from interactive.h:5,
                 from Xoractive.cpp:1:
/usr/include/c++/9/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Iterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = guess(int)::<lambda(int, int)>]':
/usr/include/c++/9/bits/stl_algo.h:81:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1920:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1952:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1967:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:4899:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = guess(int)::<lambda(int, int)>]'
Xoractive.cpp:72:6:   required from here
/usr/include/c++/9/bits/predefined_ops.h:143:18: error: void value not ignored as it ought to be
  143 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = int; _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = guess(int)::<lambda(int, int)>]':
/usr/include/c++/9/bits/stl_algo.h:1827:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1884:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1970:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:4899:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = guess(int)::<lambda(int, int)>]'
Xoractive.cpp:72:6:   required from here
/usr/include/c++/9/bits/predefined_ops.h:215:11: error: void value not ignored as it ought to be
  215 |  { return bool(_M_comp(__val, *__it)); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Value = int; _Compare = guess(int)::<lambda(int, int)>]':
/usr/include/c++/9/bits/stl_heap.h:133:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_heap.h:237:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_heap.h:342:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1671:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1932:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1947:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1967:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<guess(int)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:4899:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = guess(int)::<lambda(int, int)>]'
Xoractive.cpp:72:6:   required from here
/usr/include/c++/9/bits/predefined_ops.h:177:11: error: void value not ignored as it ought to be
  177 |  { return bool(_M_comp(*__it, __val)); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~