Submission #516296

#	Time	Username	Problem	Language	Result	Execution time	Memory
516296		LeonaRaging	Cipele (COCI18_cipele)	C++14	0 / 90	1070 ms	2996 KiB

cipele

/*
rikka simp
　　　 　 　 　 　 　 　 /⌒ヽ
　　　　　　　　　　　　|/ ⌒　 ＿＿＿_
　　　　　　　　　　　　| ..: : : : : : : : : : : : ＞
　　　　　　　　　　　イ: : : ／ : : : : : : : : : : : ｀ヽ　　/￣〉
　　　　　 ､_＿_.／: : : : :/:| : : : : : : : : : !: : V: :ハ /　 /
　　　　　　　　/: : : : : :/　|: : : | :/＼: : |: : : |: : : {＿_ ￣}
　　　　 　 　 /: : : |/|:/､ﾐｉ|: : : |/ 斗 ヽ:!: : : !: : : }ヽ:.}￣
　　　　 　/⌒{: :: :.7笊ぅﾚ､: :| ん笊ぅ.}: : : |: : : |: :V
　　　　　弋__八: : | 弋+ツ　　　弋+ .ツ}: : : : : : :|: ハ
　　　　　　　 |　}.⊂⊃　　＿＿ 　 ⊂⊃: : :/､: : | : ハ
　　　　　　　 |..八 　 　 〈/ 　 　}　　　;′:/ / : 人: : ::}
　　　　 　 　 ヽ 　＞ . 　 ＼__.ノ　　 /: : :ﾚ': ／　　）ノ
　　　　　　　　 ヽ　　　≧ーｧ―‐ｧ.厶ｲ (￣)
　　　　　　　　 　 ＼　 ／　 ／　 　 　 V三}


*/
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const ll maxn = 1e5 + 5;
const int mod = 1e9 + 7;

int n, m;
vector<int> a, b;

int Find(int x, int first)
{
    int l = first, r = m, pos = 1e9;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (b[mid] >= x)
        {
            pos = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return pos;
}

int check(int m)
{
    int pos = 0;
    for (int i = 0; i < n; i++)
    {
        int idx = Find(a[i] - m, pos);
        if (idx == 1e9) return 0;
        if (abs(b[idx] - a[i]) > m) return 0;
        pos = idx + 1;
    }
    return 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("test.INP","r",stdin);
    //freopen("test.OUT","w",stdout);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int x; cin >> x;
        a.push_back(x);
    }
    for (int i = 0; i < m; i++)
    {
        int x; cin >> x;
        b.push_back(x);
    }
    if (n > m)
    {
        swap(n, m);
        swap(a, b);
    }
    sort(a.begin(), a.end()); sort(b.begin(),b.end());
    int l = 1, r = 1e9, ans;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else l = m + 1;
    }
    cout << ans << "\n";
}

Compilation message (stderr)

cipele.cpp: In function 'int main()':
cipele.cpp:94:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |     cout << ans << "\n";
      |                    ^~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9