cf1214F

cf1214F

Description

Two large companies “Cecsi” and “Poca Pola” are fighting against each other for a long time. In order to overcome their competitor, “Poca Pola” started a super secret project, for which it has total n vacancies in all of their offices. After many tests and interviews n candidates were selected and the only thing left was their employment.

Because all candidates have the same skills, it doesn’t matter where each of them will work. That is why the company decided to distribute candidates between workplaces so that the total distance between home and workplace over all candidates is minimal.

It is well known that Earth is round, so it can be described as a circle, and all m cities on Earth can be described as points on this circle. All cities are enumerated from 1 to m so that for each i (1≤i≤m−1) cities with indexes i and i+1 are neighbors and cities with indexes 1 and m are neighbors as well. People can move only along the circle. The distance between any two cities equals to minimal number of transitions between neighboring cities you have to perform to get from one city to another. In particular, the distance between the city and itself equals 0.

The “Poca Pola” vacancies are located at offices in cities a1,a2,…,an. The candidates live in cities b1,b2,…,bn. It is possible that some vacancies are located in the same cities and some candidates live in the same cities.

The “Poca Pola” managers are too busy with super secret project, so you were asked to help “Poca Pola” to distribute candidates between workplaces, so that the sum of the distance between home and workplace over all candidates is minimum possible.

Input

The first line contains two integers m and n (1≤m≤109, 1≤n≤200000) — the number of cities on Earth and the number of vacancies.

The second line contains n integers a1,a2,a3,…,an (1≤ai≤m) — the cities where vacancies are located.

The third line contains n integers b1,b2,b3,…,bn (1≤bi≤m) — the cities where the candidates live.

Output

The first line should contain the minimum total distance between home and workplace over all candidates.

The second line should contain n different integers from 1 to n. The i-th of them should be the index of candidate that should work at i-th workplace.

Sample Input

1
2
3
10 3
1 5 5
10 4 6

Sample Output

1
2
3
1 2 3

Solution

先给出不会证明正确性的 $O(n^2)$ 代码

1
2
3
4
5
6
for(int i=1;i<=n;i++){
int cur=0;
for(int j=1;j<=n;j++)
cur+=dis(a[j],b[(i+j-2)%n+1]);
ans=min(ans,cur);
}

然后考虑一个分段函数

枚举 $i$ ,把 $a_1$ 对应 $b_i$ 的情况的答案设为 $ans_i$

同理

注意两个不等式不等价,比如 $a_i=b_j$ 的时候一个符号为正一个符号为负,使用尺取即可, 细节见代码把

Code

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define ll long long
#define FIO "cf1214F"
using namespace std;

const int N=2e5+5;

int n;
double m;

struct node{
int id,x;
inline void rd(const int &i){scanf("%d",&x);id=i;}
inline bool operator <(const node &t)const{
return x<t.x;
}
}a[N],b[N];

ll ans[N];
int out[N];

int flag;

inline void add(int x,int l,int r,int v){
if(l>r)return;
if(flag){
l=(n+x-l)%n+1;
r=(n+x-r)%n+1;
swap(l,r);
}else{
l=(l+n-x)%n+1;
r=(r+n-x)%n+1;
}

if(l>r){
ans[l]+=v;
ans[1]+=v;
ans[r+1]-=v;
}else{
ans[l]+=v;
ans[r+1]-=v;
}
}

inline void getans(node *a,node *b){
//1~j1 j1+1~j2 j2+1~j3 j3+1~n
// ai-m/2 ai ai+m/2

for(int i=1,j1=0,j2=0,j3=0;i<=n;i++){
while(b[j1+1].x<a[i].x-m/2&&j1<n)j1++;
while(b[j2+1].x<a[i].x&&j2<n)j2++;
if(!flag)while(b[j2+1].x<=a[i].x&&j2<n)j2++;
while(b[j3+1].x<=a[i].x+m/2&&j3<n)j3++;
add(i,1,j1,-a[i].x);
add(i,j1+1,j2,a[i].x);
add(i,j2+1,j3,-a[i].x);
add(i,j3+1,n,a[i].x);

if(!flag){
add(i,1,j1,m);
add(i,j3+1,n,m);
}
}
}

int main(){
freopen(FIO".in","r",stdin);
//freopen(FIO".out","w",stdout);
scanf("%lf%d",&m,&n);
for(int i=1;i<=n;i++)a[i].rd(i);
for(int i=1;i<=n;i++)b[i].rd(i);
sort(a+1,a+n+1);
sort(b+1,b+n+1);

getans(a,b);
flag=1;
getans(b,a);

for(int i=1;i<=n;i++)ans[i]+=ans[i-1];

int mn=1;
for(int i=1;i<=n;i++)if(ans[i]<ans[mn])mn=i;
printf("%lld\n",ans[mn]);

for(int i=1;i<=n;i++)
out[a[i].id]=b[(i+mn-2)%n+1].id;

return 0;
}