Submission #412838

#	Time	Username	Problem	Language	Result	Execution time	Memory
412838		cadmiumsky	Xor Sort (eJOI20_xorsort)	C++14	100 / 100	10 ms	1024 KiB

xorsort

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int v[1001];
int temp[1001];
int ind[1001];


vector< pair<int,int> > solution;

static inline void pushsol(int x, int y) {
  solution.push_back({x+1,y+1});
  v[x]^=v[y];
}
static void printsol() {
  //for(int i=0; i<5; i++) {
    //cout << v[i] <<' ';
  //}
  //cout << "\n\n";
  cout << solution.size() <<'\n';
  for(int i=0; i<solution.size(); i++) {
    cout << solution[i].first <<' ' << solution[i].second <<'\n';
  }
  exit(0);
}

static void solve2(int n, int bit) {
  if(bit<0 || n<=0)
    return;
  int poz=-1;
  for(int i=0; i<n; i++) {
    temp[i]=v[i];
  }
  for(int i=0; i<n; i++) {
    if(v[i]&(1<<bit)) {
      poz=i;
      break;
    }
  }
  if(poz==-1) {
    solve2(n,bit-1);
    return;
  }
  for(int i=poz+1; i<n; i++) {
    if(!(temp[i]&(1<<bit)))
      pushsol(i,i-1);
  }
  for(int i=poz; i<n-1; i++) {
    pushsol(i,i+1);
  }
  solve2(n-1,bit-1);
  return;
}
static void solve1(int n) {
  if(n<=0)
    return;
  int poz=ind[n-1];
  for(int i=poz+1; i<n; i++)
    pushsol(i,i-1);
  for(int i=poz-2; i>=0; i--) 
    pushsol(i,i+1);
  for(int i=0; i<n-1; i++)
    pushsol(i,i+1);
  for(int i=0; i<n-1; i++) {
    if(ind[i]>ind[n-1])
      ind[i]--;
  }
  solve1(n-1);
}

static bool cmp(int x, int y) {
  return v[x]<v[y];
}

int main() {
  int s,n;
  cin >> n >> s;
  for(int i=0; i<n; i++)
    cin >> v[i],ind[i]=i;
  if(s==2) {
    solve2(n,20);
    printsol();
  }
  else {
    sort(ind,ind+n,cmp);
    for(int i=0; i<n-1; i++)
      pushsol(i,i+1);
    solve1(n);
    printsol();
  }
} 
/*
 * 12 23 34 45 5
 * 
 * 
 */ 

Compilation message (stderr)

xorsort.cpp: In function 'void printsol()':
xorsort.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int i=0; i<solution.size(); i++) {
      |                ~^~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40