QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#221145#6838. Assumption is All You NeedrealIyxiang#WA 0ms5848kbC++141.4kb2023-10-21 10:09:302023-10-21 10:09:31

Judging History

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

  • [2023-10-21 10:09:31]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5848kb
  • [2023-10-21 10:09:30]
  • 提交

answer

#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 1e6 + 10;

int n, a[N], b[N];

int get(int *a, int x) {
	rep(i, 1, n) if(a[i] == x) return i;
	return -1;
}

void solve() {
	n = in; rep(i, 1, n) a[i] = in; rep(i, 1, n) b[i] = in;
	veg ans;
	rep(i, 1, n) {
		int ta = get(a, i), tb = get(b, i);
		if(ta < tb) return puts("-1"), void();
		per(j, ta - 1, tb) {
			if(a[j] > i) swap(a[j], a[ta]), ans.eb(j, ta), ta = j;
		} //cerr << tb << " " << i << endl;
		assert(a[tb] == i);
	}
	printf("%lu\n", ans.size());
	for(auto v : ans) printf("%d %d\n", v.fi, v.se);
}

int main() {
#ifdef YJR_2333_TEST
	freopen("1.in", "r", stdin);
#endif
	for(int T = in; T; T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5848kb

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: 5800kb

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
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-1
0
0
-1
-1
0
-1
-1
-1
1
1 2
-1
2
1 2
2 3
-1
-1
0
-1
-1
2
2 3
3 4
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
1
1 2
-1
-1
-1
...

result:

wrong answer Case #2: Jury has the answer but participant has not