이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define sze(x) (ll) x.size()
#define idx(x, a) get<x>(a)
#define LID(x) (x << 1LL)
#define RID(x) (x << 1LL) + 1LL
#define ID(x) (x + MAXN)
#define CONV(x) (x - MAXN)
#define countbit(x) __builtin_popcountll(x)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pi;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r)
{
return uniform_int_distribution<ll>(l, r)(rng);
}
inline ll lcm(ll u, ll v)
{
return u * v / __gcd(u, v);
}
const ll MAXN = 1e5 + 3;
const ll INF = 1e18;
pi a[MAXN];
ll b[MAXN];
ll k, n, m, res = 0;
ll solve(ll u, ll v)
{
ll rt = 0;
for (ll i = 1; i <= n; ++i)
{
ll mn = min(abs(a[i].fi - u) + abs(a[i].se - u) + 1, abs(a[i].fi - v) + abs(a[i].se - v) + 1);
rt += mn;
}
return rt;
}
ll comp(ll x, ll y)
{
return (x > y ? 1 : (x < y ? -1 : 0));
}
void solve1()
{
ll x = b[m / 2];
for (ll i = 1; i <= n; ++i)
{
ll rt = abs(a[i].fi - x) + abs(a[i].se - x) + 1;
res += rt;
}
cout << res;
}
void solve2()
{
ll rt = INF;
for (ll l = 1; l <= m; ++l)
{
ll pre = INF;
for (ll r = l + 1; r <= m; ++r)
{
ll tans = solve(l, r);
if (pre < tans) break;
pre = min(pre, tans);
}
rt = min(rt, pre);
}
res += rt;
cout << res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef OFFLINE
freopen("input.inp", "r", stdin);
#endif
ll _;
cin >> k >> _;
n = 0, m = 0;
ll mn = INF, mx = -INF;
set<ll> s;
for (ll i = 1; i <= _; ++i)
{
char c1, c2; ll p1, p2; cin >> c1 >> p1 >> c2 >> p2;
if (c1 == c2) res += abs(p1 - p2);
else
{
b[++m] = p1, b[++m] = p2;
a[++n] = {p1, p2};
}
}
sort(b + 1, b + m + 1);
if (k == 1) solve1();
else solve2();
}
컴파일 시 표준 에러 (stderr) 메시지
bridge.cpp: In function 'int main()':
bridge.cpp:99:8: warning: unused variable 'mn' [-Wunused-variable]
99 | ll mn = INF, mx = -INF;
| ^~
bridge.cpp:99:18: warning: unused variable 'mx' [-Wunused-variable]
99 | ll mn = INF, mx = -INF;
| ^~
# | 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... |