ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209846 | #3778. 交换乘积 | qiuqiu | 100 | 126ms | 3252kb | C++11 | 1020b | 2024-08-05 09:52:46 | 2024-08-05 12:13:31 |
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize(2)
int a[1005],b[1005],l[1005];
vector<int> ans;
struct node{
int key,val;
} c[1005],d[1005];
bool cmp(node a,node b){return a.val<b.val;}
struct ys{
int u,v;
};
ys p[1005];
bool cmp2(ys a,ys b){return a.v<b.v;}
void bubble(int n){
for(int i=1;;i++){
bool k=1;
for(int j=1;j<=n-i;j++){
if(l[j]>l[j+1]){
ans.push_back(j);
k=0;
swap(l[j],l[j+1]);
}
}
if(k) return;
}
}
signed main(){
int n;
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",a+i),c[i].key=i,c[i].val=a[i];
for(int i=1;i<=n;i++) scanf("%lld",b+i),d[i].key=i,d[i].val=b[i];
sort(c+1,c+n+1,cmp);
sort(d+1,d+n+1,cmp);
int cnt=0;
for(int i=1;i<=n;i++) cnt+=c[i].val*d[i].val,p[i].u=c[i].key,p[i].v=d[i].key;
printf("%lld\n",cnt);
sort(p+1,p+n+1,cmp2);
for(int i=1;i<=n;i++) l[p[i].u]=i;
bubble(n);
printf("%lld\n",(int)ans.size());
for(auto i:ans) printf("%lld ",i);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1216kb
input:
10 2 6 6 7 7 8 9 9 9 10 1 2 2 2 4 4 4 5 8 9
output:
343 0
result:
ok Accepted
Test #2:
score: 10
Accepted
time: 0ms
memory: 1300kb
input:
300 3 7 16 23 27 28 30 31 31 33 39 39 40 41 45 52 54 57 60 76 77 80 82 83 84 87 95 96 99 101 102 102...
output:
100081185 23 31 32 33 68 78 82 114 142 152 156 172 191 200 208 217 229 248 255 263 264 31 32 263
result:
ok Accepted
Test #3:
score: 10
Accepted
time: 0ms
memory: 1272kb
input:
1000 5877 11223 46751 56288 84111 90383 107139 123175 189078 189840 201516 206791 212484 235460 2355...
output:
31886434041864508 0
result:
ok Accepted
Test #4:
score: 10
Accepted
time: 3ms
memory: 1588kb
input:
300 850 586 11 803 499 983 491 676 654 701 902 727 76 292 948 875 126 701 815 10 614 170 207 109 3 3...
output:
30126307 22523 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 27 28 29 30 31 32 33 ...
result:
ok Accepted
Test #5:
score: 10
Accepted
time: 41ms
memory: 3252kb
input:
1000 2303 71258 47543 27966 78350 51973 54564 93554 93120 22126 73773 37093 33624 99015 98835 72871 ...
output:
33644571203 259886 2 3 5 6 8 9 10 11 12 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ...
result:
ok Accepted
Test #6:
score: 10
Accepted
time: 0ms
memory: 1336kb
input:
100 96840 47122 5255 76197 81892 650 34013 82490 89220 60416 42623 1755 82567 10753 20425 70135 4333...
output:
357435899115 2347 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 23 24 25 26 27 28 29 30 31 32 33...
result:
ok Accepted
Test #7:
score: 10
Accepted
time: 29ms
memory: 3248kb
input:
800 6547222 7373197 3093209 5574969 3392784 6785440 1906423 4960424 1000638 4591726 9150475 1385022 ...
output:
26926720212052531 159242 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ...
result:
ok Accepted
Test #8:
score: 10
Accepted
time: 21ms
memory: 3248kb
input:
1000 350 868 622 692 210 3582 3414 2296 2391 1002 1607 945 111 478 424 661 3009 2223 2397 2168 1618 ...
output:
5358834254 255622 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24 25 26 27 28 30 31 32 33 34 3...
result:
ok Accepted
Test #9:
score: 10
Accepted
time: 15ms
memory: 3248kb
input:
1000 1 2 1 2 1 1 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 1 2 1 1 1 2 1 1 1 1 2 1 2 2 1 2 1 1 1 1 1 1 1 1 1 1...
output:
2507 165499 1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ...
result:
ok Accepted
Test #10:
score: 10
Accepted
time: 17ms
memory: 3248kb
input:
1000 4326892 2791949 5730257 8195022 6651135 6011847 9951798 1049226 2435447 2097834 7158411 7162178...
output:
34200287502289533 258080 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30...
result:
ok Accepted
Extra Test:
score: 0
Extra Test Passed