QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236902#6838. Assumption is All You NeedAndy#WA 1ms3540kbC++201.4kb2023-11-04 11:25:142023-11-04 11:25:15

Judging History

你现在查看的是最新测评结果

  • [2023-11-04 11:25:15]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3540kb
  • [2023-11-04 11:25:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
	char c=getchar();
	int f=1,x=0;
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
	return f*x;
}
void solve();
int main(){
	cin.tie(0)->sync_with_stdio(false);
	int t=1;
	cin>>t;
	while(t--)solve();
	return 0;
}

const int N=3000;
int a[N],b[N],ia[N],ib[N];
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ia[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
		ib[b[i]]=i;
	}
	
	set<int>s1,s2;
	
	s1.insert(ia[n]);
	s2.insert(ib[n]);
	
	
	vector<pair<int,int>>V;
	for(int i=n-1;i;i--){
		
		
		vector<int>S1,S2;
		for(auto w:s1)S1.push_back(w);
		for(auto w:s2)S2.push_back(w);
		
		for(int i=0;i<S1.size();i++)if(S1[i]>S2[i]){
			cout<<-1<<endl;
			return;
		}
		
		int p=lower_bound(S1.begin(),S1.end(),ia[i])-S1.begin();
		int q=lower_bound(S2.begin(),S2.end(),ib[i])-S2.begin();
		
		
		if(q<p){
			V.emplace_back(ib[i],S2[q]);
			for(int j=q;j<p-1;j++)V.emplace_back(S2[j],S2[j+1]);
		}
		else if(q>p){
			V.emplace_back(S2[q-1],ib[i]);
			for(int j=q-1;j>p;j--)V.emplace_back(S2[j],S2[j-1]);
		}
		
		s1.insert(ia[i]);
		s2.insert(ib[i]);
	}
	
	cout<<V.size()<<endl;
	
	for(auto i=V.rbegin();i!=V.rend();i++){
		cout<<(i->first)<<" "<<(i->second)<<endl;
	}
	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3444kb

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 2
2 4
7
7 8
6 7
5 6
4 5
3 4
2 3
1 2

result:

ok T=3

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3540kb

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
...

output:

-1
30
9 10
8 9
7 8
6 7
5 6
4 5
3 4
2 3
5 4
6 5
7 6
8 7
9 8
9 10
8 9
7 8
6 7
5 6
4 5
3 4
8 9
7 8
6 8
5 6
4 5
8 9
6 8
5 6
1 5
5 8
7
4 5
3 4
2 3
1 2
5 6
2 3
2 4
-1
-1
-1
-1
-1
0
-1
-1
-1
9
5 6
4 5
3 4
2 3
1 2
4 3
5 4
5 6
4 5
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
5
4 5
3 4
2 3
1 2
3 4
-1
-1
-1
-1
-1
-...

result:

wrong answer 9-th operation (5, 4) not valid: (x < y) == false