QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#111633 | #6511. Balancing Sequences | AFewSuns | WA | 14ms | 3616kb | C++14 | 2.3kb | 2023-06-07 19:58:22 | 2023-06-07 19:58:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 8e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
vector<pair<ll,ll> > ans;
ll t,n,a[4040],b[4040],mp[4040];
int main(){
t=read();
while(t--){
n=read();
for(ll i=0;i<2*n;i+=2) a[i]=read();
for(ll i=1;i<2*n;i+=2) a[i]=read();
for(ll i=0;i<2*n;i+=2) b[i]=read();
for(ll i=1;i<2*n;i+=2) b[i]=read();
fr(i,0,2*n-1) mp[b[i]]=i;
bl ck=0;
fr(i,1,2*n){
ll pos=0;
fr(j,0,2*n-1) if(a[j]==i) pos=j;
if(pos==mp[i]) continue;
if(a[pos]<a[pos^1]){
ck=1;
break;
}
if(a[mp[i]]>a[mp[i]^1]){
swap(a[pos],a[mp[i]]);
ans.push_back(MP(pos,mp[i]));
continue;
}
ll minn=inf,tmp;
fr(j,0,2*n-1){
if(a[j]>i&&a[j]>a[j^1]&&minn>a[j]){
minn=a[j];
tmp=j;
}
}
if(minn==inf||minn>a[mp[i]]){
ck=1;
break;
}
swap(a[mp[i]^1],tmp);
ans.push_back(MP(mp[i]^1,tmp));
swap(a[pos],a[mp[i]]);
ans.push_back(MP(pos,mp[i]));
}
if(ck) writeln(-1);
else{
writeln(ans.size());
fr(i,0,(ll)ans.size()-1) pf("%lld %lld %lld %lld\n",ans[i].fir%2+1,ans[i].fir/2+1,ans[i].sec%2+1,ans[i].sec/2+1);
}
ans.clear();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
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: 14ms
memory: 3616kb
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 -1 -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 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
result:
wrong answer you didn't find a solution but jury did. (test case 50)