QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110296 | #6511. Balancing Sequences | Qingyu | WA | 319ms | 3436kb | C++23 | 1.6kb | 2023-06-01 14:49:22 | 2023-06-01 14:49:25 |
Judging History
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)