Problem - 1684C - Codeforces
题意:
现在有一个n*m的棋盘，每个棋子有一个值，你可以交换两列棋盘的棋子位置，使得每一行的棋子从左到右为非递减。
题解:
只需要判断一行不满足的即可，因为如果最后有答案，那么每一行的交换一定是相同的，所以判断一行即可。分两种情况，连续两个递减，连续三个递减，很明显，如果又连续三个递减的数字，那么，如果有答案，俺么答案只能是交换第一个和最后一个,例如:6 2 1,只有交换6和1才有可能。连续两个递减，如果只有一组，那么就是这一组的两个点，但如果有多组，例如:6 2 3 1，很明显，我们应该交换的是第一组的左端点后最后一组的右端点。所以，连续两个递减，就不断更新右端点即可。交换后判断一遍是否递增即可。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int N=5e5+50;
map<ll,map<ll,ll>> mp;
signed main(){
ll t;cin>>t;
while(t--){
ll n,m;cin>>n>>m;
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++){
cin>>mp[i][j];
}
ll l=-1,r=-1;
for(ll i=1;i<=n;i++){
ll sum=0;
for(ll j=1;j<=m;j++){
if(mp[i][j]<mp[i][j-1]){
sum++;
}
else sum=0;
if(sum==1){
if(l==-1) l=j-1;
r=j;
while(r+1<=m&&mp[i][r+1]==mp[i][r]){
r++;
}
while(l-1>=1&&mp[i][l-1]==mp[i][l]){
l--;
}
}
else if(sum==2) {r=j;break;}
}
if(l!=-1&&r!=-1) break;
}
for(ll i=1;i<=n;i++){
swap(mp[i][l],mp[i][r]);
}
ll flag=0;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
if(mp[i][j]<mp[i][j-1]) {flag=1;break;}
}
if(flag) break;
}
if(flag) cout<<"-1"<<endl;
else if(l==-1&&r==-1) cout<<"1 1"<<endl;
else cout<<l<<" "<<r<<endl;
}
}
