#include <bits/stdc++.h>
using namespace std;
int tab[1009];
bool zaj[1100000];
vector<pair<int,int>>odp;
int xorr(int a, int b)
{
int u=1;
int wynik=0;
while(a>0||b>0)
{
if(a%2!=b%2)
{
wynik+=u;
}
a=a/2;
b=b/2;
u=u*2;
}
return wynik;
}
void swap_true(int a, int b)
{
tab[a]=xorr(tab[a],tab[b]);
}
void swapp(int a, int b)
{
/**swap_true(a,b);
swap_true(b,a);
swap_true(a,b);**/
odp.push_back({a,b});
odp.push_back({b,a});
odp.push_back({a,b});
swap(tab[a],tab[b]);
}
int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
srand(time(0));
int n,s;cin>>n>>s;
for(int i=1;i<=n;i++)
{
cin>>tab[i];
zaj[tab[i]]=1;
}
if(s==1)
{
for(int i=1;i<=n*3;i++)
{
int a=(rand()%n)+1;
int b=rand()%2;
if(a==1||(b%2==1&&a!=n))
{
if(tab[a]>tab[a+1])
{
if(zaj[xorr(tab[a],tab[a+1])]==0)
{
odp.push_back({a,a+1});
zaj[tab[a]]=0;
swap_true(a,a+1);
zaj[tab[a]]=1;
}
}
}
else
{
if(tab[a]>tab[a-1])
{
if(zaj[xorr(tab[a],tab[a-1])]==0)
{
odp.push_back({a,a-1});
zaj[tab[a]]=0;
swap_true(a,a-1);
zaj[tab[a]]=1;
}
}
}
}
}
else
{
for(int i=1;i<=n*3;i++)
{
int a=(rand()%n)+1;
int b=rand()%2;
if(a==1||(b%2==1&&a!=n))
{
if(tab[a]>tab[a+1])
{
odp.push_back({a,a+1});
swap_true(a,a+1);
}
}
else
{
if(tab[a]>tab[a-1])
{
odp.push_back({a,a-1});
swap_true(a,a-1);
}
}
}
}
vector<pair<int,int>>U;
for(int i=1;i<=n;i++)
{
U.push_back({tab[i],i});
}
sort(U.begin(),U.end());
for(int i=0;i<U.size();i++)
{
int minn=2000000000;
int ind=U[i].second;
for(int j=ind;j-1>=i;j--)
{
swapp(j,j-1);
}
}
cout<<odp.size()<<endl;
for(int i=0;i<odp.size();i++)
{
cout<<odp[i].first<<" "<<odp[i].second<<endl;
}
/**for(int i=1;i<=n;i++)
{
cout<<tab[i]<<endl;
}**/
return 0;
}
Compilation message
xorsort.cpp: In function 'int main()':
xorsort.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int i=0;i<U.size();i++)
| ~^~~~~~~~~
xorsort.cpp:111:13: warning: unused variable 'minn' [-Wunused-variable]
111 | int minn=2000000000;
| ^~~~
xorsort.cpp:119:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i=0;i<odp.size();i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Integer 0 violates the range [1, 5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Integer 0 violates the range [1, 5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Integer 0 violates the range [1, 5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
