Main Idea:↵
Instead of directly comparing permutations,I transformed each permutation and required permutation into a number that allows prefix matching efficiently.After doing i just have to find the permutation which is nearest to reruired permutation .↵
↵
↵
Complexity:↵
O(n * m * log n)↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
↵
const int BASE = 11;↵
↵
/*↵
Find how many digits are different↵
from the back while comparing hashes↵
*/↵
int common(int x,int y){↵
↵
int cnt=0;↵
↵
while(x!=y){↵
x/=BASE;↵
y/=BASE;↵
cnt++;↵
}↵
↵
return cnt;↵
}↵
↵
/*↵
Binary search the closest hash↵
and return minimum mismatch count↵
*/↵
int best(int n,vector<int> &a,int m){↵
↵
int st=0,end=a.size()-1;↵
↵
while(st<=end){↵
↵
int mid=(st+end)/2;↵
↵
if(a[mid]<=n){↵
st=mid+1;↵
}↵
else{↵
end=mid-1;↵
}↵
}↵
↵
int ans=m;↵
↵
// check upper bound candidate↵
if(st<a.size()){↵
ans=min(ans,common(n,a[st]));↵
}↵
↵
// check lower bound candidate↵
if(end>=0){↵
ans=min(ans,common(n,a[end]));↵
}↵
↵
return ans;↵
}↵
↵
int32_t main() {↵
↵
int t;↵
cin>>t;↵
↵
while(t--){↵
↵
int n,m;↵
cin>>n>>m;↵
↵
vector<int> equ(n),req(n);↵
↵
for(int i=0;i<n;i++){↵
↵
vector<int> a(m);↵
↵
for(int j=0;j<m;j++){↵
cin>>a[j];↵
a[j]--;↵
}↵
↵
/*↵
temp -> original permutation hash↵
treq -> inverse permutation hash↵
*/↵
↵
int temp=0,treq=0;↵
↵
// create original permutation hash↵
for(int j=0;j<m;j++){↵
temp=temp*BASE+a[j];↵
}↵
↵
// build inverse permutation↵
vector<int> pos(m);↵
↵
for(int j=0;j<m;j++){↵
pos[a[j]]=j;↵
}↵
↵
// create inverse permutation hash↵
for(int j=0;j<m;j++){↵
treq=treq*BASE+pos[j];↵
}↵
↵
req[i]=temp;↵
equ[i]=treq;↵
}↵
↵
// sort inverse hashes for binary search↵
sort(equ.begin(),equ.end());↵
↵
vector<int> ans(n);↵
↵
for(int i=0;i<n;i++){↵
↵
int cnt=best(req[i],equ,m);↵
↵
// matched prefix length↵
ans[i]=m-cnt;↵
}↵
↵
for(int i=0;i<n;i++){↵
cout<<ans[i]<<" ";↵
}↵
↵
cout<<endl;↵
}↵
}↵
~~~~~↵
↵
↵
[submission:374473747]↵
↵
↵
↵
Instead of directly comparing permutations,I transformed each permutation and required permutation into a number that allows prefix matching efficiently.After doing i just have to find the permutation which is nearest to reruired permutation .↵
↵
↵
Complexity:↵
O(n * m * log n)↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
↵
const int BASE = 11;↵
↵
/*↵
Find how many digits are different↵
from the back while comparing hashes↵
*/↵
int common(int x,int y){↵
↵
int cnt=0;↵
↵
while(x!=y){↵
x/=BASE;↵
y/=BASE;↵
cnt++;↵
}↵
↵
return cnt;↵
}↵
↵
/*↵
Binary search the closest hash↵
and return minimum mismatch count↵
*/↵
int best(int n,vector<int> &a,int m){↵
↵
int st=0,end=a.size()-1;↵
↵
while(st<=end){↵
↵
int mid=(st+end)/2;↵
↵
if(a[mid]<=n){↵
st=mid+1;↵
}↵
else{↵
end=mid-1;↵
}↵
}↵
↵
int ans=m;↵
↵
// check upper bound candidate↵
if(st<a.size()){↵
ans=min(ans,common(n,a[st]));↵
}↵
↵
// check lower bound candidate↵
if(end>=0){↵
ans=min(ans,common(n,a[end]));↵
}↵
↵
return ans;↵
}↵
↵
int32_t main() {↵
↵
int t;↵
cin>>t;↵
↵
while(t--){↵
↵
int n,m;↵
cin>>n>>m;↵
↵
vector<int> equ(n),req(n);↵
↵
for(int i=0;i<n;i++){↵
↵
vector<int> a(m);↵
↵
for(int j=0;j<m;j++){↵
cin>>a[j];↵
a[j]--;↵
}↵
↵
/*↵
temp -> original permutation hash↵
treq -> inverse permutation hash↵
*/↵
↵
int temp=0,treq=0;↵
↵
// create original permutation hash↵
for(int j=0;j<m;j++){↵
temp=temp*BASE+a[j];↵
}↵
↵
// build inverse permutation↵
vector<int> pos(m);↵
↵
for(int j=0;j<m;j++){↵
pos[a[j]]=j;↵
}↵
↵
// create inverse permutation hash↵
for(int j=0;j<m;j++){↵
treq=treq*BASE+pos[j];↵
}↵
↵
req[i]=temp;↵
equ[i]=treq;↵
}↵
↵
// sort inverse hashes for binary search↵
sort(equ.begin(),equ.end());↵
↵
vector<int> ans(n);↵
↵
for(int i=0;i<n;i++){↵
↵
int cnt=best(req[i],equ,m);↵
↵
// matched prefix length↵
ans[i]=m-cnt;↵
}↵
↵
for(int i=0;i<n;i++){↵
cout<<ans[i]<<" ";↵
}↵
↵
cout<<endl;↵
}↵
}↵
~~~~~↵
↵
↵
[submission:374473747]↵
↵
↵
↵
