QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110296#6511. Balancing SequencesQingyuWA 319ms3436kbC++231.6kb2023-06-01 14:49:222023-06-01 14:49:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-01 14:49:25]
  • 评测
  • 测评结果:WA
  • 用时:319ms
  • 内存:3436kb
  • [2023-06-01 14:49:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
#define templ template<typename T>
templ bool chkmin(T &x,T y){return x>y?x=y,1:0;}
templ bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
#define sz 4333

int n;
int a[2][sz],b[2][sz];
pii posA[sz],posB[sz];

vector<pair<pii,pii>>ans;
void SWAP(pii fr,pii to) {
	swap(a[fr.fir][fr.sec],a[to.fir][to.sec]);
	swap(posA[a[fr.fir][fr.sec]],posA[a[to.fir][to.sec]]);
	ans.push_back({fr,to});;
}

void work() {
	ans.clear();
	cin>>n;
	rep(x,0,1) rep(i,1,n) cin>>a[x][i],posA[a[x][i]]={x,i};
	rep(x,0,1) rep(i,1,n) cin>>b[x][i],posB[b[x][i]]={x,i};
	static int del[sz];
	rep(i,1,n) del[i]=0;
	rep(i,1,n*2) {
		if (posA[i]!=posB[i]) {
			if (i<a[posA[i].fir^1][posA[i].sec]) return cout<<"-1\n",void();
			int to=posB[i].sec;
			if (a[posB[i].fir][to]>a[posB[i].fir^1][to]) {
				SWAP(posA[i],posB[i]);
				continue;
			}
			int flg=0;
			rep(j,i+1,a[posB[i].fir][to]-1) if (a[posA[j].fir^1][posA[j].sec]<i) {
				SWAP(posA[j],posB[i]);
				SWAP(posA[i],posB[i]);
				flg=1;
				break;
			}
			if (!flg) return cout<<"-1\n",void();
		}
	}
	cout<<ans.size()<<'\n';
	for (auto [x,y]:ans) cout<<x.fir+1<<' '<<x.sec<<' '<<y.fir+1<<' '<<y.sec<<'\n';
}

int main() {
    file();
	int T; cin>>T;
	while (T--) work();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3436kb

input:

2
2
1 2
3 4
4 3
2 1
3
1 2 4
3 5 6
1 2 4
5 3 6

output:

-1
1
2 1 2 2

result:

ok correct plan (nYES = 1, nNO = 1) (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 319ms
memory: 3424kb

input:

100000
3
1 6 4
2 3 5
5 6 1
3 4 2
3
3 5 2
6 1 4
4 3 5
6 2 1
3
6 4 3
2 5 1
1 4 5
2 3 6
3
4 2 3
6 1 5
3 1 4
5 2 6
3
4 3 1
5 2 6
4 3 6
5 1 2
3
1 5 6
3 2 4
2 3 5
6 1 4
3
2 5 4
6 1 3
6 3 2
5 4 1
3
3 6 5
2 1 4
3 5 4
2 6 1
3
5 6 3
2 4 1
3 4 6
2 5 1
3
4 5 6
2 3 1
1 2 3
4 6 5
3
3 2 1
6 4 5
3 1 5
2 4 6
3
5 2 3...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4
1 1 2 3
1 2 2 3
1 2 1 1
1 2 1 3
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
2 3 1 1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
2 2 1 1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

wrong answer invalid operation 1 1 2 3 (test case 50)