QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #293268 | #7956. Walk Swapping | hank55663 | WA | 0ms | 4200kb | C++14 | 4.6kb | 2023-12-29 03:11:24 | 2023-12-29 03:11:25 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define pdd pair<double,double>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define mp make_pair
#define LL long long
#define ULL unsigned long long
#define sqr(x) ((x)*(x))
#define pi acos(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
using namespace std;
int S[3005];
void add(int x,int k){
x++;
for(int i = x;i<3005;i+=i&-i){
S[i]+=k;
}
}
int query(int x){
x++;
int res=0;
for(int i=x;i>0;i-=i&-i){
res+=S[i];
}
return res;
}
vector<int> v[3005];
void solve(int T){
int n;
scanf("%d",&n);
int a[3005],b[3005];
int ta[3005],tb[3005];
for(int i = 0;i<n;i++){
scanf("%d",&a[i]);
ta[i]=a[i];
}
for(int i = 0;i<n;i++){
scanf("%d",&b[i]);
tb[i]=b[i];
}
sort(ta,ta+n);
sort(tb,tb+n);
for(int i = 0;i<n;i++){
if(ta[i]!=tb[i]){
printf("-1\n");
return;
}
}
for(int i = 0;i<n;i++)ta[i]=a[i],tb[i]=b[i];
int ans=1e9;
for(int t=0;t<2;t++){
// printf("%d\n",t);
for(int i = 0;i<n;i++){
int val[3005];
int tot1=0,tot2=0;
int pre[3005],pre2[3005];
pre[0]=0;
pre2[0]=0;
for(int j =0;j<n;j++){
val[j]=0;
pre[j+1]=pre[j];
pre2[j+1]=pre2[j];
if(a[j]==b[j]){
val[j]|=1;
tot1++;
pre[j+1]++;
}
if(a[j]==b[(j+1)%n]){
val[j]|=2;
tot2++;
pre2[j+1]++;
}
// printf("(%d %d)",a[j],val[j]);
}
// printf("%d %d\n",tot1,tot2);
if(tot1==n){
ans=min(ans,i*(n-1));
// printf("!%d %d\n",i,n-1);
}
else{
vector<int> tw,z;
for(int j = 0;j<n;j++){
if(val[j]==2)tw.pb(j);
if(val[j]==0)z.pb(j);
}
if(z.size()>1){
for(int i = n-1;i>0;i--){
swap(a[i],a[i-1]);
}
continue;
}
if(z.size()==1){
int x=z[0];
x=(x+n-1)%n;
int tot=0;
int cnt=0;
int need1=n-1;
while(tot!=tw.size()){
cnt++;
if(val[x]==2)tot++;
if(val[x]==3)tot1--;
if(val[x]==1)tot1=-1;
need1--;
x=(x+n-1)%n;
}
if(need1==tot1){
ans=min(ans,i*(n-1)+cnt);
// printf("%d %d\n",i,cnt);
}
}
else{
for(int i = 0;i+1<tw.size();i++){
if(-pre[tw[i]]+pre[tw[i+1]+1]==tw[i+1]-1-tw[i]){
if(tot2-(-pre2[tw[i]]+pre2[tw[i+1]+1])+tw[i+1]-1-tw[i]==n){
ans=min(ans,i*(n-1)+n-(tw[i+1]-1-tw[i])-1);
// printf("%d %d\n",i,n-(tw[i+1]-1-tw[i])-1);
}
}
}
if(pre[tw[0]]+pre[n]-pre[tw.back()+1]==tw[0]-1+n-tw.back()){
if(tot2-(pre2[n]-pre2[tw.back()]+pre2[tw[0]+1])+tw[0]-1-tw.back()+n==n){
ans=min(ans,i*(n-1)+n-(tw[0]-1-tw.back()+n)-1);
// printf("%d %d\n",i,n-(tw[0]-1-tw.back()+n)-1);
}
}
}
}
// printf("%d\n",n-1);
for(int i = n-1;i>0;i--){
swap(a[i],a[i-1]);
}
// for(int i = 0 ;i<n;i++)printf("%d ",a[i]);
// printf("\n");
}
for(int i = 0;i<n;i++){
a[i]=ta[i];
b[i]=tb[i];
}
reverse(a,a+n);
reverse(b,b+n);
}
if(ans==1e9)ans=-1;
printf("%d\n",ans);
}
int main(){
srand(time(NULL));
int t=1;
// scanf("%d",&t);
for(int i = 1;i<=t;i++){
// cerr<<i<<endl;
solve(i);
}
}
/*
1227076727
1919786269
1261786217
1924134973
1051246577
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3956kb
input:
4 4 3 2 1 3 4 2 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
6 2 1 1 2 2 1 1 2 2 2 1 1
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4200kb
input:
6 4 1 3 6 2 5 6 2 1 3 4 5
output:
-1
result:
ok single line: '-1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
4 1 2 3 4 4 2 1 3
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
6 4 1 3 6 2 5 6 2 5 3 4 1
output:
13
result:
ok single line: '13'
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3960kb
input:
6 4 1 3 3 2 5 3 2 5 3 4 1
output:
-1
result:
wrong answer 1st lines differ - expected: '12', found: '-1'