Submission #1118148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118148		Pannda	Measures (CEOI22_measures)	C++17	10 / 100	1542 ms	6472 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 5;
int n, m, d;

int a[N], b[N];

bool csub2(){
    if(n > 200'000 || m > 10) return false;
    return true;
}
namespace sub2{
    void solve(){
        // N > 0
        for(int i = 1; i <= m; i++){
            a[++n] = b[i];
            sort(a + 1, a + n + 1);
            int lo = 0, hi = 1e15, res = -1;
            while(lo <= hi){
                int mid = (lo + hi) / 2;

                int last = -1e18;

                bool flag = true;
                for(int j = 1; j <= n; j++){
                    int pos = max(a[j] - mid, last + d);
                    if(pos - a[j] > mid) flag = false;
                    last = pos;
                }

                if(flag){
                    res = mid, hi = mid - 1;
                } else{
                    lo = mid + 1;
                }
            }
            cout << res / 2 << (res % 2 == 1 ? ".5" : "") << " ";
        }
    }
}

bool csub3(){
    for(int i = 2; i <= m; i++){
        if(b[i] < b[i - 1]) return false;
    }
    return true;
}
namespace sub3{
    void solve(){
        // N = 0
        int last = -1e18, ans = 0;
        for(int i = 1; i <= m; i++){
            int lo = ans, hi = 1e15, res = -1;
            while(lo <= hi){
                int mid = (lo + hi) / 2;

                if(b[i] + mid - d >= last - mid){
                    res = mid, hi = mid - 1;
                } else{
                    lo = mid + 1;
                }
                last = a[i];
            }
            last = b[i];
            ans = max(ans, res);
            cout << ans / 2 << (ans % 2 == 1 ? ".5" : "") << " ";
        }
    }
}

namespace full{
    void solve(){
        // N = 0

        for(int i = 1; i <= m; i++){

        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> d;
    for(int i = 1; i <= n; i++){
        cin >> a[i]; a[i] *= 2;
    }

    for(int i = 1; i <= m; i++){
        cin >> b[i]; b[i] *= 2;
    }

    d *= 2;

    return sub2::solve(), 0;
    return 0;
}

/*
2 1 2
1 3
2

0 5 3
1 2 3 4 5

3 3 3
3 3 3
3 3 3
*/

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41