Submission #1073758

#TimeUsernameProblemLanguageResultExecution timeMemory
1073758raduvXor Sort (eJOI20_xorsort)C++17
100 / 100
6 ms1240 KiB
#include <bits/stdc++.h> //#define DEBUG 1 using namespace std; const int MAXN = 1'000; const int MAXSUM = 100'000; const int MAXBIT = 19; int v[MAXN + 1]; vector<pair<int, int>> op; signed main() { int n, t, i, u, p, cn; scanf("%d%d", &n, &t); for( i = 1; i <= n; i++ ){ scanf("%d", &v[i]); } if( t == 1 ){ // select sort ca de ce nu? ( n <= 200 ) for( u = n; u > 1; u-- ){ p = 1; for( i = 1; i <= u; i++ ){ if(v[p] < v[i]) p = i; } for( i = 1; i < u; i++ ) op.push_back({i, i + 1}); for( i = p + 1; i <= u; i++ ) op.push_back({i, i - 1}); for( i = p - 2; i >= 1; i-- ) op.push_back({i, i + 1}); for( i = p; i < n; i++ ) swap(v[i], v[i + 1]); } for( i = n; i >= 2; i-- ) op.push_back({i - 1, i}); } else{ cn = n; for( p = MAXBIT; p >= 0; p-- ){ for( i = 1; i < cn; i++ ){ if(v[i] & (1 << p)){ if( v[i + 1] & (1 << p)){ op.push_back({i, i + 1}); v[i] ^= v[i + 1]; } else{ op.push_back({i + 1, i}); // au ambele bitul maxim (1 << p) acum op.push_back({i, i + 1}); // iar acum nu mai are niciunul bitul (1 << p) v[i + 1] ^= v[i]; v[i] ^= v[i + 1]; } } } while( cn > 1 && (v[cn] & (1 << p))) cn--; } } printf("%d\n", (int)op.size()); for( auto pi : op ) printf("%d %d\n", pi.first, pi.second); #ifdef DEBUG for( i = 1; i <= n; i++ ) printf("%d ", v[i]); #endif // DEBUG return 0; }

Compilation message (stderr)

xorsort.cpp: In function 'int main()':
xorsort.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d%d", &n, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~
xorsort.cpp:15:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |       scanf("%d", &v[i]);
      |       ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...