oj.uz

Submission #1118148

# Submission time Handle Problem Language Result Execution time Memory
1118148 2024-11-25T04:36:23 Z Pannda Measures (CEOI22_measures) C++17
10 / 100
 1500 ms 6472 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2384 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Correct 3 ms 2384 KB Output is correct
5 Correct 2 ms 2560 KB Output is correct
6 Correct 3 ms 2384 KB Output is correct
7 Correct 3 ms 2384 KB Output is correct
8 Correct 2 ms 2384 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2384 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Correct 3 ms 2384 KB Output is correct
5 Correct 2 ms 2560 KB Output is correct
6 Correct 3 ms 2384 KB Output is correct
7 Correct 3 ms 2384 KB Output is correct
8 Correct 2 ms 2384 KB Output is correct
9 Runtime error 141 ms 6472 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

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

Subtask #4
0 / 41.0

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