oj.uz

Submission #516296

# Submission time Handle Problem Language Result Execution time Memory
516296 2022-01-21T04:02:53 Z LeonaRaging Cipele (COCI18_cipele) C++14
0 / 90
 1000 ms 2996 KB 
/*
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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 2884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1037 ms 2996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1022 ms 2652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 2816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 2624 KB Time limit exceeded
2 Halted 0 ms 0 KB -