oj.uz

Submission #560216

# Submission time Handle Problem Language Result Execution time Memory
560216 2022-05-11T07:18:40 Z AGE Cipele (COCI18_cipele) C++14
90 / 90
 979 ms 8344 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define int long long
using namespace std;
const int N=1e5+5,M=2e3+10,mod=100000000000031;
vector<int>v;

long long  summ(long long  x,long long  y){
    return ((x%mod)+(y%mod))%mod;
}

long long  mult(long long  x,long long  y){
    return ((x%mod)*(y%mod))%mod;
}

int n,m,a[N],b[N],c[N];
bool ok(int mid){

    multiset<int>st;

    for(int i=0;i<n;i++)
        st.insert(-a[i]);

    int i=0,okk=0;

    while(i<m){

        while(st.size()!=0&&abs(b[i]-abs(*st.begin()))>mid)
            st.erase(st.begin());

        if(st.size()==0){
            okk=1;
            break;
        }

        i++;
        st.erase(st.begin());

    }

    return !okk;
}
main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++)
        cin>>a[i];

    for(int i=0;i<m;i++)
        cin>>b[i];

    if(n<m){
        for(int i=0;i<m;i++)
            c[i]=b[i],b[i]=a[i],a[i]=c[i];

        swap(n,m);
    }

    sort(b,b+m);
    reverse(b,b+m);

    int l=0,r=1e9;

    while(l<r){

        int mid=(l+r)/2;

        if(ok(mid))
            r=mid;

        else l=mid+1;

    }

    cout<<r<<endl;


    return 0;
}

Compilation message

cipele.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main()
      | ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 6548 KB Output is correct
2 Correct 979 ms 6552 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 6544 KB Output is correct
2 Correct 949 ms 8344 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 468 KB Output is correct
2 Correct 32 ms 768 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 672 KB Output is correct
2 Correct 31 ms 764 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 648 KB Output is correct
2 Correct 27 ms 724 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 668 KB Output is correct
2 Correct 27 ms 724 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 672 KB Output is correct
2 Correct 26 ms 704 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 957 ms 7224 KB Output is correct
2 Correct 490 ms 5016 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 6860 KB Output is correct
2 Correct 534 ms 6604 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 6648 KB Output is correct
2 Correct 802 ms 7128 KB Output is correct