Submission #519231

#TimeUsernameProblemLanguageResultExecution timeMemory
519231Ai7081Xoractive (IZhO19_xoractive)C++17
100 / 100
3 ms448 KiB
#include <bits/stdc++.h> using namespace std; vector<int> a; int ask(int i);/* { return a[i]; }*/ vector<int> get_pairwise_xor(vector<int> pos);/* { vector<int> ret; for (auto i : pos) { for (auto j : pos) ret.push_back(a[i]^a[j]); } sort(ret.begin(), ret.end()); return ret; }*/ vector<int> guess(int n) { vector<int> ret(n); ret[0] = ask(1); //cout << "ret[0] : " << ret[0] << endl; vector<int> q; vector<vector<int>> bit(7); for (int i=0; i<7; i++) { //cout << "i " << i << endl; q.clear(); for (int j=1; j<=n; j++) { if ((j>>i)%2 && j>1) q.push_back(j);//, cout << "push " << j << endl; } if (q.empty()) continue; vector<int> res1, res2; res1 = get_pairwise_xor(q); q.push_back(1); res2 = get_pairwise_xor(q); /* cout << "res1 : "; for (auto it : res1) cout << it << ' '; cout << endl << "res2 : "; for (auto it : res2) cout << it << ' '; cout << endl; */ int ii=0, jj=1; vector<int> tmp; while (ii<res1.size() && jj<res2.size()) { if (res1[ii] > res2[jj]) { tmp.push_back(res2[jj]); jj++; } else if (res1[ii] == res2[jj]) { ii++; jj++; } } while (jj < res2.size()) { tmp.push_back(res2[jj]); jj++; } for (int j=0; j<tmp.size(); j+=2) bit[i].push_back(tmp[j] ^ ret[0]); /* cout << "bit " << i << " : "; for (auto it : bit[i]) cout << it << ' '; cout << endl; */ } vector<pair<int, int>> v; for (int i=0; i<7; i++) { for (auto x : bit[i]) { bool ok = false; for (int j=0; j<v.size(); j++) { if (x == v[j].first) { v[j].second += (1<<i); ok = true; break; } } if (!ok) { v.push_back({x, (1<<i)}); } } } for (auto [x, idx] : v) ret[idx-1] = x; return ret; } /* int main() { a = {0, 2, 4, 3, 109}; vector<int> g = guess(4); cout << "ans : "; for (auto x : g) cout << x << ' '; } */

Compilation message (stderr)

Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         while (ii<res1.size() && jj<res2.size()) {
      |                ~~^~~~~~~~~~~~
Xoractive.cpp:46:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         while (ii<res1.size() && jj<res2.size()) {
      |                                  ~~^~~~~~~~~~~~
Xoractive.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         while (jj < res2.size()) {
      |                ~~~^~~~~~~~~~~~~
Xoractive.cpp:60:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int j=0; j<tmp.size(); j+=2) bit[i].push_back(tmp[j] ^ ret[0]);
      |                       ~^~~~~~~~~~~
Xoractive.cpp:72:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for (int j=0; j<v.size(); j++) {
      |                           ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...