QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#665683 | #6838. Assumption is All You Need | hhdhh | TL | 1ms | 3636kb | C++23 | 2.0kb | 2024-10-22 14:44:18 | 2024-10-22 14:44:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define rept(i, a, ne) for(int i = (a); ~i ; i=ne[i])
#define debug(x) cout<<#x<<": "<<x<<endl
#define fi first
#define sec second
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int>PII;
const int N=3e3+10;
int a[N];
int b[N];
PII res[N*N];
int c[N];
int d[N];
int u=0;
void slove()
{
u++;
int n;
cin>>n;
rep(i,1,n)
{
cin>>a[i];
c[a[i]]=i;
}
rep(i,1,n)
{
cin>>b[i];
d[b[i]]=i;
}
int num=0;
per(i,n,1)
{
while(1)
{
if(c[i]==d[i])break;
int mai=0;
rep(j,c[i]+1,d[i])
{
if(a[j]>i)
continue;
if(mai==0)
mai=j;
else if(mai<a[j])
mai=j;
}
if(mai==0&&u==52)
{
while(1);
}
if(mai==0||a[mai]>=i)
{
cout<<-1<<endl;
return;
}
int p=a[mai];
swap(a[c[i]],a[mai]);
swap(c[i],c[p]);
res[++num]={c[i],c[p]};
}
}
rep(i,1,n)
{
if(a[i]!=b[i])
{
cout<<-1<<endl;
return;
}
}
cout<<num<<endl;
rep(i,1,num)
{
if(res[i].fi>res[i].sec)
{
swap(res[i].fi,res[i].sec);
}
cout<<res[i].fi<<' '<<res[i].sec<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// cout << fixed << setprecision(9);
int t=1;
cin>>t;
while(t--)
{
slove();
}
return 0;
}
//#pragma GCC optimize(2)
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3636kb
input:
3 2 1 2 2 1 4 4 1 2 3 1 3 2 4 8 8 7 6 5 4 3 2 1 1 8 7 6 5 4 3 2
output:
-1 2 1 4 1 2 7 1 2 1 3 1 4 1 5 1 6 1 7 1 8
result:
ok T=3
Test #2:
score: -100
Time Limit Exceeded
input:
315 10 8 4 6 1 2 9 7 5 10 3 6 7 8 10 5 1 3 2 9 4 10 10 8 2 9 6 5 7 4 3 1 7 1 3 5 9 8 4 10 6 2 6 4 6 5 3 1 2 1 5 4 6 2 3 12 5 9 12 8 10 6 11 4 2 3 1 7 9 2 3 1 5 12 4 7 6 10 8 11 10 4 7 3 2 8 9 6 10 5 1 1 4 8 10 3 7 9 6 2 5 7 1 2 4 5 6 7 3 4 3 5 6 7 2 1 3 1 3 2 2 1 3 7 1 5 3 7 6 4 2 6 5 2 1 3 4 7 1 1 ...