Submission #775081

#TimeUsernameProblemLanguageResultExecution timeMemory
775081daoquanglinh2007Xor Sort (eJOI20_xorsort)C++17
65 / 100
7 ms1236 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair <int, int> #define fi first #define se second #define mp make_pair #define getbit(x, i) ((x&(1<<i)) != 0) const int NM = 1000; int N, S, a[NM+5]; vector <pii> ans; void op(int i, int j){ ans.push_back(mp(i, j)); a[i] ^= a[j]; } void solve1(){ bool back = 0; while (true){ bool ok = 1; if (!back){ for (int i = 1; i < N; i++) if (a[i] > a[i+1]){ ok = 0; op(i+1, i); op(i, i+1); op(i+1, i); } } else{ for (int i = N-1; i >= 1; i--) if (a[i] > a[i+1]){ ok = 0; op(i+1, i); op(i, i+1); op(i+1, i); } } if (ok) break; back = !back; } } void solve2(){ int tar = N+1; for (int i = 19; i >= 0; i--){ bool ok = 0; for (int j = 1; j <= N; j++) if (getbit(a[j], i)){ ok = 1; break; } if (ok == 0) continue; tar--; for (int j = 1; j < tar; j++) if (getbit(a[j], i) && !getbit(a[j+1], i)){ op(j+1, j); op(j, j+1); } else if (getbit(a[j], i) && getbit(a[j+1], i)){ op(j, j+1); } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> S; for (int i = 1; i <= N; i++) cin >> a[i]; if (S == 1) solve1(); else solve2(); cout << ans.size() << '\n'; for (int i = 0; i < ans.size(); i++) cout << ans[i].fi << ' ' << ans[i].se << '\n'; return 0; }

Compilation message (stderr)

xorsort.cpp: In function 'int main()':
xorsort.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0; i < ans.size(); i++)
      |                  ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...