We hope that you have enjoyed this round! Here is the sketch of solutions for the problems. ↵
### [A. Array and Peaks](https://codeforces.net/contest/1513/problem/A)↵
↵
- Problem Setter: [user:ajit,2021-04-11]↵
- Editorialist: [user:ajit,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513A]↵
</spoiler>↵
↵
<spoiler summary="Implementation in C++">↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
int main()↵
{↵
int tests;↵
cin>>tests;↵
while(tests--)↵
{↵
int n,k;↵
cin>>n>>k;↵
vector<int> ans(n+1);↵
int num=n;↵
for(int i=2;i<n;i+=2)↵
{↵
if(k==0)break;↵
ans[i]=num--;↵
k--;↵
}↵
if(k)↵
{↵
cout<<-1<<endl;↵
continue;↵
}↵
int cur=1;↵
for(int i=1;i<=n;i++)↵
{↵
if(!ans[i])↵
ans[i]=cur++;↵
}↵
↵
for(int i=1;i<=n;i++)↵
cout<<ans[i]<<" ";↵
cout<<endl;↵
}↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
### [B. AND Sequences](https://codeforces.net/contest/1513/problem/B)↵
↵
- Problem Setter: [user:ajit,2021-04-11]↵
- Editorialist: [user:ajit,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513B]↵
</spoiler>↵
↵
<spoiler summary="Implementation in C++">↵
↵
~~~~~↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solveTestCase()↵
{↵
int MOD=1e9+7;↵
int n;↵
cin>>n;↵
vector<int> a(n);↵
for(int i=0;i<n;i++)cin>>a[i];↵
↵
int min1=*min_element(a.begin(),a.end());↵
int cnt=0;↵
↵
for(int x:a)↵
{↵
if(min1==x)cnt++;↵
if((min1&x)!=min1)↵
{↵
printf("0\n");↵
return;↵
}↵
}↵
↵
int fact=1;↵
for(int i=1;i<=n-2;i++)fact=(1LL*fact*i)%MOD;↵
int ans=(1LL * cnt * (cnt-1))%MOD;↵
ans = (1LL * ans * fact) % MOD;↵
printf("%d\n",ans);↵
}↵
↵
int main()↵
{↵
int tests;↵
cin>>tests;↵
while(tests--)↵
solveTestCase();↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
### [C. Add One](https://codeforces.net/contest/1513/problem/C)↵
↵
- Problem Setter: [user:kalpitk,2021-04-11]↵
- Editorialist: [user:dvshah,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513C]↵
</spoiler>↵
↵
<spoiler summary="Implementation in C++">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define int long long↵
↵
const int max_n = 200005, mod = 1000000007;↵
int dp[max_n];↵
↵
signed main(){↵
↵
for(int i=0; i<9; i++)dp[i] = 2;↵
dp[9] = 3;↵
for(int i=10; i<max_n; i++){↵
dp[i] = (dp[i-9] + dp[i-10])%mod;↵
}↵
↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int t;↵
cin>>t;↵
while(t--){↵
int n, m;↵
cin>>n>>m;↵
int ans = 0;↵
while(n > 0){↵
int x = n%10;↵
ans += ((m + x < 10) ? 1 : dp[m + x - 10]);↵
ans %= mod;↵
n/=10;↵
}↵
cout<<ans<<"\n";↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
### [D. GCD and MST](https://codeforces.net/contest/1513/problem/D)↵
↵
- Problem Setter: [user:ajit,2021-04-11]↵
- Editorialist: [user:ajit,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513D]↵
</spoiler>↵
↵
<spoiler summary="Implementation in C++">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solveTestCase()↵
{↵
int n,x;↵
cin>>n>>x;↵
vector<int> a(n);↵
for(int i=0;i<n;i++)cin>>a[i];↵
↵
//tells whether vertices i and i+1 are connected for 0<=i<n-1↵
vector<bool> isConnected(n);↵
vector<pair<int,int>> vals;↵
↵
for(int i=0;i<n;i++)↵
vals.push_back(make_pair(a[i],i));↵
↵
sort(vals.begin(),vals.end());↵
long long int ans=0;↵
for(auto p:vals)↵
{↵
int cur_val=p.first;↵
int i=p.second;↵
↵
if(cur_val>=x)break;↵
↵
while(i>0)↵
{↵
if(isConnected[i-1])break;↵
if(a[i-1]%cur_val==0)↵
{↵
isConnected[i-1]=true;↵
ans+=cur_val;↵
i--;↵
}↵
else↵
break;↵
}↵
↵
i=p.second;↵
while(i<n-1)↵
{↵
if(isConnected[i])break;↵
if(a[i+1]%cur_val==0)↵
{↵
isConnected[i]=true;↵
ans+=cur_val;↵
i++;↵
}↵
else↵
break;↵
}↵
↵
}↵
↵
for(int i=0;i<n-1;i++)↵
{↵
if(!isConnected[i])↵
ans+=x;↵
}↵
↵
cout<<ans<<endl;↵
}↵
↵
int main()↵
{↵
int T;↵
cin>>T;↵
while(T--)↵
{↵
solveTestCase();↵
} ↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
### [E. Cost Equilibrium](https://codeforces.net/contest/1513/problem/E)↵
↵
- Problem Setter: [user:7dan,2021-04-11]↵
- Editorialist: [user:kalpitk,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513E]↵
</spoiler>↵
↵
<spoiler summary="Implementation in C++">↵
↵
~~~~~↵
#include "bits/stdc++.h"↵
#define ll long long↵
#define MOD 1000000007↵
ll power(ll x,ll y, ll md=MOD){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}↵
↵
using namespace std;↵
↵
#define int long long↵
↵
#define MAX 100005↵
↵
vector<int> f(MAX);↵
vector<int> inv(MAX);↵
↵
void init() {↵
f[0] = 1;↵
for(int i=1;i<MAX;i++) f[i] = (f[i-1]*i)%MOD;↵
inv[MAX-1] = power(f[MAX-1], MOD-2, MOD);↵
for(int i=MAX-2;i>=0;i--) inv[i] = (inv[i+1]*(i+1)) % MOD;↵
↵
for(int i=0;i<MAX;i++) assert(inv[i]==power(f[i],MOD-2,MOD));↵
}↵
↵
int ncr(int n, int r) {↵
if(r > n || r < 0) return 0;↵
↵
int ans = f[n];↵
ans *= (inv[r] * inv[n - r]) % MOD;↵
ans %= MOD;↵
↵
return ans;↵
}↵
↵
int solve(const vector<int> &v) {↵
↵
int n = v.size();↵
int s = 0;↵
for(auto x: v) s += x;↵
↵
if(!(s % n == 0)) return 0;↵
↵
int src = 0;↵
int snk = 0;↵
↵
map<int,int> freqSrc, freqSnk;↵
for(auto x: v) {↵
if(s / n < x) {↵
freqSrc[x]++;↵
src ++;↵
}↵
if(s / n > x) {↵
freqSnk[x]++;↵
snk ++;↵
}↵
}↵
↵
if(src == 0 && snk == 0) return 1;↵
↵
if(src == 1 || snk == 1) {↵
int ans = f[n];↵
for(auto x: freqSnk) {↵
ans = (ans * inv[x.second]) % MOD;↵
}↵
for(auto x: freqSrc) {↵
ans = (ans * inv[x.second]) % MOD;↵
}↵
ans *= inv[n - src - snk];↵
ans %= MOD;↵
return ans;↵
}↵
↵
int ans = (2 * f[src] * f[snk]) % MOD;↵
↵
// Divide by freq of repeating elements↵
for(auto x: freqSnk) {↵
ans = (ans * inv[x.second]) % MOD;↵
}↵
for(auto x: freqSrc) {↵
ans = (ans * inv[x.second]) % MOD;↵
}↵
↵
int tot = src + snk;↵
int left = n - tot;↵
↵
// Number of Solution: x_0 + x_1 + x_2 + ... + x_tot = left↵
ans = (ans * ncr(left + tot, tot)) % MOD;↵
return ans;↵
}↵
↵
signed main() {↵
↵
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
↵
init();↵
↵
int n;↵
cin>>n;↵
↵
vector<int> v(n);↵
for(auto &x: v) cin>>x;↵
↵
cout<<solve(v);↵
↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [F. Swapping Problem](https://codeforces.net/contest/1513/problem/F)↵
↵
- Problem Setter: [user:7dan,2021-04-11]↵
- Editorialist: [user:mtnshh,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513F]↵
</spoiler>↵
↵
<spoiler summary="Implementation1 in C++">↵
↵
~~~~~↵
#include "bits/stdc++.h"↵
#define ll long long↵
#define MOD 1000000007↵
#define inf 1000000000000000000LL↵
↵
using namespace std;↵
↵
#define int long long↵
↵
↵
signed main() {↵
↵
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
↵
int n;↵
cin>>n;↵
↵
vector<int> a(n), b(n);↵
for(auto &x: a) cin>>x;↵
for(auto &x: b) cin>>x;↵
↵
map<int,int> segX, segY;↵
↵
for(int i=0;i<n;i++) {↵
if(a[i]<=b[i]) {↵
if(!segX.count(a[i])) segX[a[i]] = b[i];↵
else segX[a[i]] = max(segX[a[i]], b[i]);↵
}↵
else {↵
if(!segY.count(b[i])) segY[b[i]] = a[i];↵
else segY[b[i]] = max(segY[b[i]], a[i]);↵
}↵
}↵
↵
// Construct prefix maxima↵
int mx = -inf;↵
for(auto &x: segX) {↵
mx = max(mx, x.second);↵
x.second = mx;↵
}↵
↵
mx = -inf;↵
for(auto &x: segY) {↵
mx = max(mx, x.second);↵
x.second = mx;↵
}↵
↵
↵
// Find best swap↵
int mxGain = 0;↵
for(int i=0;i<n;i++) {↵
if(a[i]<=b[i]) {↵
auto it = segY.upper_bound(a[i]);↵
if(it==segY.begin()) continue;↵
↵
it--;↵
int overlap = min(it->second, b[i]) - a[i];↵
mxGain = max(mxGain, 2*overlap);↵
}↵
else {↵
auto it = segX.upper_bound(b[i]);↵
if(it==segX.begin()) continue;↵
↵
it--;↵
int overlap = min(it->second, a[i]) - b[i];↵
mxGain = max(mxGain, 2*overlap);↵
}↵
}↵
↵
// Find ans = initial val - mxGain↵
int ans = 0;↵
for(int i=0;i<n;i++) {↵
ans += abs(a[i]-b[i]);↵
}↵
↵
ans -= mxGain;↵
cout<<ans;↵
↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation2 in C++">↵
~~~~~↵
// created by mtnshh↵
↵
#include<bits/stdc++.h>↵
#include<algorithm>↵
using namespace std;↵
↵
#define ll long long↵
#define ld long double↵
↵
#define rep(i,a,b) for(ll i=a;i<b;i++)↵
#define repb(i,a,b) for(ll i=a;i>=b;i--)↵
↵
#define pb push_back↵
#define all(A) A.begin(),A.end()↵
#define allr(A) A.rbegin(),A.rend()↵
#define ft first↵
#define sd second↵
↵
#define pll pair<ll,ll>↵
#define V vector<ll>↵
#define S set<ll>↵
#define VV vector<V>↵
#define Vpll vector<pll>↵
↵
#define endl "\n"↵
↵
const ll logN = 20;↵
const ll M = 1000000007;↵
const ll INF = 1e18;↵
#define PI 3.14159265↵
↵
const ll N = 100005;↵
↵
int main(){↵
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);↵
ll n;↵
cin >> n;↵
↵
ll A[n], B[n];↵
↵
rep(i,0,n) cin >> A[i];↵
rep(i,0,n) cin >> B[i];↵
↵
Vpll x1, x2, y1, y2;↵
↵
ll ans = 0;↵
↵
rep(i,0,n){↵
↵
ans += abs(A[i]-B[i]);↵
↵
if(A[i]<B[i]){↵
x1.pb({A[i], B[i]});↵
x2.pb({B[i], A[i]});↵
}↵
else{↵
y1.pb({A[i], B[i]});↵
y2.pb({B[i], A[i]});↵
}↵
}↵
↵
ll fin = ans;↵
↵
// ↵
↵
set<ll> s1;↵
↵
sort(all(x1));↵
sort(all(y2));↵
↵
ll cur1 = 0;↵
↵
for(auto i: x1){↵
↵
while(cur1 < y2.size() and y2[cur1].ft <= i.ft){↵
s1.insert(y2[cur1].sd);↵
cur1++;↵
}↵
↵
if(s1.size() > 0){↵
ll last = *s1.rbegin();↵
fin = min(fin, ans - 2 * (min(i.sd, last) - i.ft));↵
}↵
↵
}↵
↵
set<ll> s2;↵
↵
sort(all(x1));↵
sort(all(y2));↵
↵
ll cur2 = 0;↵
↵
for(auto i: y2){↵
↵
while(cur2 < x1.size() and x1[cur2].ft <= i.ft){↵
s2.insert(x1[cur2].sd);↵
cur2++;↵
}↵
↵
if(s2.size() > 0){↵
ll last = *s2.rbegin();↵
fin = min(fin, ans - 2 * (min(last, i.sd) - i.ft));↵
}↵
↵
}↵
↵
cout << fin << endl;↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
### [A. Array and Peaks](https://codeforces.net/contest/1513/problem/A)↵
↵
- Problem Setter: [user:ajit,2021-04-11]↵
- Editorialist: [user:ajit,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513A]↵
</spoiler>↵
↵
<spoiler summary="Implementation in C++">↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
int main()↵
{↵
int tests;↵
cin>>tests;↵
while(tests--)↵
{↵
int n,k;↵
cin>>n>>k;↵
vector<int> ans(n+1);↵
int num=n;↵
for(int i=2;i<n;i+=2)↵
{↵
if(k==0)break;↵
ans[i]=num--;↵
k--;↵
}↵
if(k)↵
{↵
cout<<-1<<endl;↵
continue;↵
}↵
int cur=1;↵
for(int i=1;i<=n;i++)↵
{↵
if(!ans[i])↵
ans[i]=cur++;↵
}↵
↵
for(int i=1;i<=n;i++)↵
cout<<ans[i]<<" ";↵
cout<<endl;↵
}↵
}↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
### [B. AND Sequences](https://codeforces.net/contest/1513/problem/B)↵
↵
- Problem Setter: [user:ajit,2021-04-11]↵
- Editorialist: [user:ajit,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513B]↵
</spoiler>↵
↵
<spoiler summary="Implementation in C++">↵
↵
~~~~~↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solveTestCase()↵
{↵
int MOD=1e9+7;↵
int n;↵
cin>>n;↵
vector<int> a(n);↵
for(int i=0;i<n;i++)cin>>a[i];↵
↵
int min1=*min_element(a.begin(),a.end());↵
int cnt=0;↵
↵
for(int x:a)↵
{↵
if(min1==x)cnt++;↵
if((min1&x)!=min1)↵
{↵
printf("0\n");↵
return;↵
}↵
}↵
↵
int fact=1;↵
for(int i=1;i<=n-2;i++)fact=(1LL*fact*i)%MOD;↵
int ans=(1LL * cnt * (cnt-1))%MOD;↵
ans = (1LL * ans * fact) % MOD;↵
printf("%d\n",ans);↵
}↵
↵
int main()↵
{↵
int tests;↵
cin>>tests;↵
while(tests--)↵
solveTestCase();↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
### [C. Add One](https://codeforces.net/contest/1513/problem/C)↵
↵
- Problem Setter: [user:kalpitk,2021-04-11]↵
- Editorialist: [user:dvshah,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513C]↵
</spoiler>↵
↵
<spoiler summary="Implementation in C++">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define int long long↵
↵
const int max_n = 200005, mod = 1000000007;↵
int dp[max_n];↵
↵
signed main(){↵
↵
for(int i=0; i<9; i++)dp[i] = 2;↵
dp[9] = 3;↵
for(int i=10; i<max_n; i++){↵
dp[i] = (dp[i-9] + dp[i-10])%mod;↵
}↵
↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int t;↵
cin>>t;↵
while(t--){↵
int n, m;↵
cin>>n>>m;↵
int ans = 0;↵
while(n > 0){↵
int x = n%10;↵
ans += ((m + x < 10) ? 1 : dp[m + x - 10]);↵
ans %= mod;↵
n/=10;↵
}↵
cout<<ans<<"\n";↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
### [D. GCD and MST](https://codeforces.net/contest/1513/problem/D)↵
↵
- Problem Setter: [user:ajit,2021-04-11]↵
- Editorialist: [user:ajit,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513D]↵
</spoiler>↵
↵
<spoiler summary="Implementation in C++">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solveTestCase()↵
{↵
int n,x;↵
cin>>n>>x;↵
vector<int> a(n);↵
for(int i=0;i<n;i++)cin>>a[i];↵
↵
//tells whether vertices i and i+1 are connected for 0<=i<n-1↵
vector<bool> isConnected(n);↵
vector<pair<int,int>> vals;↵
↵
for(int i=0;i<n;i++)↵
vals.push_back(make_pair(a[i],i));↵
↵
sort(vals.begin(),vals.end());↵
long long int ans=0;↵
for(auto p:vals)↵
{↵
int cur_val=p.first;↵
int i=p.second;↵
↵
if(cur_val>=x)break;↵
↵
while(i>0)↵
{↵
if(isConnected[i-1])break;↵
if(a[i-1]%cur_val==0)↵
{↵
isConnected[i-1]=true;↵
ans+=cur_val;↵
i--;↵
}↵
else↵
break;↵
}↵
↵
i=p.second;↵
while(i<n-1)↵
{↵
if(isConnected[i])break;↵
if(a[i+1]%cur_val==0)↵
{↵
isConnected[i]=true;↵
ans+=cur_val;↵
i++;↵
}↵
else↵
break;↵
}↵
↵
}↵
↵
for(int i=0;i<n-1;i++)↵
{↵
if(!isConnected[i])↵
ans+=x;↵
}↵
↵
cout<<ans<<endl;↵
}↵
↵
int main()↵
{↵
int T;↵
cin>>T;↵
while(T--)↵
{↵
solveTestCase();↵
} ↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
### [E. Cost Equilibrium](https://codeforces.net/contest/1513/problem/E)↵
↵
- Problem Setter: [user:7dan,2021-04-11]↵
- Editorialist: [user:kalpitk,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513E]↵
</spoiler>↵
↵
<spoiler summary="Implementation in C++">↵
↵
~~~~~↵
#include "bits/stdc++.h"↵
#define ll long long↵
#define MOD 1000000007↵
ll power(ll x,ll y, ll md=MOD){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}↵
↵
using namespace std;↵
↵
#define int long long↵
↵
#define MAX 100005↵
↵
vector<int> f(MAX);↵
vector<int> inv(MAX);↵
↵
void init() {↵
f[0] = 1;↵
for(int i=1;i<MAX;i++) f[i] = (f[i-1]*i)%MOD;↵
inv[MAX-1] = power(f[MAX-1], MOD-2, MOD);↵
for(int i=MAX-2;i>=0;i--) inv[i] = (inv[i+1]*(i+1)) % MOD;↵
↵
for(int i=0;i<MAX;i++) assert(inv[i]==power(f[i],MOD-2,MOD));↵
}↵
↵
int ncr(int n, int r) {↵
if(r > n || r < 0) return 0;↵
↵
int ans = f[n];↵
ans *= (inv[r] * inv[n - r]) % MOD;↵
ans %= MOD;↵
↵
return ans;↵
}↵
↵
int solve(const vector<int> &v) {↵
↵
int n = v.size();↵
int s = 0;↵
for(auto x: v) s += x;↵
↵
if(!(s % n == 0)) return 0;↵
↵
int src = 0;↵
int snk = 0;↵
↵
map<int,int> freqSrc, freqSnk;↵
for(auto x: v) {↵
if(s / n < x) {↵
freqSrc[x]++;↵
src ++;↵
}↵
if(s / n > x) {↵
freqSnk[x]++;↵
snk ++;↵
}↵
}↵
↵
if(src == 0 && snk == 0) return 1;↵
↵
if(src == 1 || snk == 1) {↵
int ans = f[n];↵
for(auto x: freqSnk) {↵
ans = (ans * inv[x.second]) % MOD;↵
}↵
for(auto x: freqSrc) {↵
ans = (ans * inv[x.second]) % MOD;↵
}↵
ans *= inv[n - src - snk];↵
ans %= MOD;↵
return ans;↵
}↵
↵
int ans = (2 * f[src] * f[snk]) % MOD;↵
↵
// Divide by freq of repeating elements↵
for(auto x: freqSnk) {↵
ans = (ans * inv[x.second]) % MOD;↵
}↵
for(auto x: freqSrc) {↵
ans = (ans * inv[x.second]) % MOD;↵
}↵
↵
int tot = src + snk;↵
int left = n - tot;↵
↵
// Number of Solution: x_0 + x_1 + x_2 + ... + x_tot = left↵
ans = (ans * ncr(left + tot, tot)) % MOD;↵
return ans;↵
}↵
↵
signed main() {↵
↵
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
↵
init();↵
↵
int n;↵
cin>>n;↵
↵
vector<int> v(n);↵
for(auto &x: v) cin>>x;↵
↵
cout<<solve(v);↵
↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [F. Swapping Problem](https://codeforces.net/contest/1513/problem/F)↵
↵
- Problem Setter: [user:7dan,2021-04-11]↵
- Editorialist: [user:mtnshh,2021-04-11]↵
↵
<spoiler summary="Tutorial">↵
[tutorial: 1513F]↵
</spoiler>↵
↵
<spoiler summary="Implementation1 in C++">↵
↵
~~~~~↵
#include "bits/stdc++.h"↵
#define ll long long↵
#define MOD 1000000007↵
#define inf 1000000000000000000LL↵
↵
using namespace std;↵
↵
#define int long long↵
↵
↵
signed main() {↵
↵
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
↵
int n;↵
cin>>n;↵
↵
vector<int> a(n), b(n);↵
for(auto &x: a) cin>>x;↵
for(auto &x: b) cin>>x;↵
↵
map<int,int> segX, segY;↵
↵
for(int i=0;i<n;i++) {↵
if(a[i]<=b[i]) {↵
if(!segX.count(a[i])) segX[a[i]] = b[i];↵
else segX[a[i]] = max(segX[a[i]], b[i]);↵
}↵
else {↵
if(!segY.count(b[i])) segY[b[i]] = a[i];↵
else segY[b[i]] = max(segY[b[i]], a[i]);↵
}↵
}↵
↵
// Construct prefix maxima↵
int mx = -inf;↵
for(auto &x: segX) {↵
mx = max(mx, x.second);↵
x.second = mx;↵
}↵
↵
mx = -inf;↵
for(auto &x: segY) {↵
mx = max(mx, x.second);↵
x.second = mx;↵
}↵
↵
↵
// Find best swap↵
int mxGain = 0;↵
for(int i=0;i<n;i++) {↵
if(a[i]<=b[i]) {↵
auto it = segY.upper_bound(a[i]);↵
if(it==segY.begin()) continue;↵
↵
it--;↵
int overlap = min(it->second, b[i]) - a[i];↵
mxGain = max(mxGain, 2*overlap);↵
}↵
else {↵
auto it = segX.upper_bound(b[i]);↵
if(it==segX.begin()) continue;↵
↵
it--;↵
int overlap = min(it->second, a[i]) - b[i];↵
mxGain = max(mxGain, 2*overlap);↵
}↵
}↵
↵
// Find ans = initial val - mxGain↵
int ans = 0;↵
for(int i=0;i<n;i++) {↵
ans += abs(a[i]-b[i]);↵
}↵
↵
ans -= mxGain;↵
cout<<ans;↵
↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation2 in C++">↵
~~~~~↵
// created by mtnshh↵
↵
#include<bits/stdc++.h>↵
#include<algorithm>↵
using namespace std;↵
↵
#define ll long long↵
#define ld long double↵
↵
#define rep(i,a,b) for(ll i=a;i<b;i++)↵
#define repb(i,a,b) for(ll i=a;i>=b;i--)↵
↵
#define pb push_back↵
#define all(A) A.begin(),A.end()↵
#define allr(A) A.rbegin(),A.rend()↵
#define ft first↵
#define sd second↵
↵
#define pll pair<ll,ll>↵
#define V vector<ll>↵
#define S set<ll>↵
#define VV vector<V>↵
#define Vpll vector<pll>↵
↵
#define endl "\n"↵
↵
const ll logN = 20;↵
const ll M = 1000000007;↵
const ll INF = 1e18;↵
#define PI 3.14159265↵
↵
const ll N = 100005;↵
↵
int main(){↵
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);↵
ll n;↵
cin >> n;↵
↵
ll A[n], B[n];↵
↵
rep(i,0,n) cin >> A[i];↵
rep(i,0,n) cin >> B[i];↵
↵
Vpll x1, x2, y1, y2;↵
↵
ll ans = 0;↵
↵
rep(i,0,n){↵
↵
ans += abs(A[i]-B[i]);↵
↵
if(A[i]<B[i]){↵
x1.pb({A[i], B[i]});↵
x2.pb({B[i], A[i]});↵
}↵
else{↵
y1.pb({A[i], B[i]});↵
y2.pb({B[i], A[i]});↵
}↵
}↵
↵
ll fin = ans;↵
↵
// ↵
↵
set<ll> s1;↵
↵
sort(all(x1));↵
sort(all(y2));↵
↵
ll cur1 = 0;↵
↵
for(auto i: x1){↵
↵
while(cur1 < y2.size() and y2[cur1].ft <= i.ft){↵
s1.insert(y2[cur1].sd);↵
cur1++;↵
}↵
↵
if(s1.size() > 0){↵
ll last = *s1.rbegin();↵
fin = min(fin, ans - 2 * (min(i.sd, last) - i.ft));↵
}↵
↵
}↵
↵
set<ll> s2;↵
↵
sort(all(x1));↵
sort(all(y2));↵
↵
ll cur2 = 0;↵
↵
for(auto i: y2){↵
↵
while(cur2 < x1.size() and x1[cur2].ft <= i.ft){↵
s2.insert(x1[cur2].sd);↵
cur2++;↵
}↵
↵
if(s2.size() > 0){↵
ll last = *s2.rbegin();↵
fin = min(fin, ans - 2 * (min(last, i.sd) - i.ft));↵
}↵
↵
}↵
↵
cout << fin << endl;↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
