UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209872#3778. 交换乘积yhmm10090ms3152kbC++111.2kb2024-08-05 10:13:272024-08-05 12:15:01

answer

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
long long n,a[1001],ans=0,c[1001],idx;
vector<long long>v;
struct node
{
	long long num,idx,numa;
}b[1001];
bool cmp(node X,node Y)
{
	return X.num>Y.num;
}
bool cmpb(node X,node Y)
{
	return X.idx<Y.idx;
}
long long FastReadLongLong()
{
	long long x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^48),c=getchar();
	}
	return x*f;
}
int main(){
	n=FastReadLongLong();
	for(int i=1;i<=n;i++)
	{
		a[i]=FastReadLongLong();
		c[i]=a[i];
	}
	for(int i=1;i<=n;i++)
	{
		b[i].num=FastReadLongLong();
		b[i].idx=i;
	}
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		ans+=(a[i]*b[i].num);
		b[i].numa=a[i];
	}
	sort(b+1,b+n+1,cmpb);
	for(int i=1;i<=n;i++)
	{
		if(c[i]==b[i].numa)
		{
			continue;
		}
		idx=0;
		for(int j=i+1;j<=n;j++)
		{
			if(c[j]==b[i].numa)
			{
				idx=j;
				break;
			}
		}
		for(int j=idx-1;j>=i;j--)
		{
			swap(c[j],c[j+1]);
			v.push_back(j);
		}
	}
	printf("%lld\n%lld\n",ans,v.size());
	for(int i=0;i<v.size();i++)
	{
		printf("%lld ",v[i]);
	}
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1220kb

input:

10
2 6 6 7 7 8 9 9 9 10
1 2 2 2 4 4 4 5 8 9

output:

343
5
3 2 6 5 6 

result:

ok Accepted

Test #2:

score: 10
Accepted
time: 0ms
memory: 1228kb

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
7
86 131 142 208 236 263 264 

result:

ok Accepted

Test #3:

score: 10
Accepted
time: 1ms
memory: 1200kb

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: 2ms
memory: 1432kb

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
22499
104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78...

result:

ok Accepted

Test #5:

score: 10
Accepted
time: 22ms
memory: 3144kb

input:

1000
2303 71258 47543 27966 78350 51973 54564 93554 93120 22126 73773 37093 33624 99015 98835 72871 ...

output:

33644571203
259882
226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 2...

result:

ok Accepted

Test #6:

score: 10
Accepted
time: 1ms
memory: 1280kb

input:

100
96840 47122 5255 76197 81892 650 34013 82490 89220 60416 42623 1755 82567 10753 20425 70135 4333...

output:

357435899115
2347
12 11 10 9 8 7 6 5 4 3 2 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 ...

result:

ok Accepted

Test #7:

score: 10
Accepted
time: 9ms
memory: 3152kb

input:

800
6547222 7373197 3093209 5574969 3392784 6785440 1906423 4960424 1000638 4591726 9150475 1385022 ...

output:

26926720212052531
159242
761 760 759 758 757 756 755 754 753 752 751 750 749 748 747 746 745 744 743...

result:

ok Accepted

Test #8:

score: 10
Accepted
time: 24ms
memory: 3144kb

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
241965
154 153 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 13...

result:

ok Accepted

Test #9:

score: 10
Accepted
time: 0ms
memory: 1372kb

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
9212
1 3 2 7 6 5 10 9 8 7 6 11 10 9 8 7 13 12 11 10 9 16 15 14 13 12 11 10 17 16 15 14 13 12 19...

result:

ok Accepted

Test #10:

score: 10
Accepted
time: 31ms
memory: 3148kb

input:

1000
4326892 2791949 5730257 8195022 6651135 6011847 9951798 1049226 2435447 2097834 7158411 7162178...

output:

34200287502289533
258080
594 593 592 591 590 589 588 587 586 585 584 583 582 581 580 579 578 577 576...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed