This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long int
#define endl '\n'
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pi>
#define fir first
#define sec second
#define MAXN 200005
#define mod 998244353
int calc(vector<int> &v, int x)
{
int ans = 0;
for (auto const &i : v)
ans += abs(i - x);
return ans;
}
int solve(vector<int> &v)
{
ordered_set<pi> s;
map<int, int> mp;
for (auto const &i : v)
{
s.insert({i, mp[i]});
mp[i]++;
}
int sz = v.size();
int x = (*s.find_by_order(sz / 2)).fir;
int ans = calc(v, x);
if (v.size() > 1)
{
int x = (*s.find_by_order((sz / 2) - 1)).fir;
ans = min(ans, calc(v, x));
}
return ans;
}
void solve1(int n, int k)
{
int ans = 0;
vector<int> pts;
for (int i = 0; i < n; i++)
{
char c1, c2;
int a, b;
cin >> c1 >> a >> c2 >> b;
if (c1 == c2)
{
ans += abs(a - b);
}
else
{
ans++;
pts.pb(a);
pts.pb(b);
}
}
if (!pts.size())
{
cout << ans << endl;
return;
}
sort(pts.begin(), pts.end());
ans += solve(pts);
cout << ans << endl;
}
void solve2(int n, int k)
{
vector<pi> aux;
vector<pi> v;
int ans = 0;
for (int i = 0; i < n; i++)
{
char c1, c2;
int a, b;
cin >> c1 >> a >> c2 >> b;
v.pb({a, b});
if (c1 == c2)
{
ans += abs(a - b);
}
else
{
ans++;
aux.pb({a + b, i});
}
}
if (!aux.size())
{
cout << ans << endl;
return;
}
sort(aux.begin(), aux.end());
vector<int> pts;
for (auto const &i : aux)
{
pts.pb(v[i.sec].fir);
pts.pb(v[i.sec].sec);
}
int need = ans;
vector<int> pts2;
ans += solve(pts);
while (pts.size() > 2)
{
pts2.pb(pts.back());
pts.pop_back();
pts2.pb(pts.back());
pts.pop_back();
int curr = need + solve(pts) + solve(pts2);
ans = min(ans, curr);
}
cout << ans << endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> k >> n;
if (k == 1)
solve1(n, k);
else
solve2(n, k);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |