oj.uz

Submission #1118173

# Submission time Handle Problem Language Result Execution time Memory
1118173 2024-11-25T04:54:55 Z pemguimn Measures (CEOI22_measures) C++14
24 / 100
 1500 ms 5200 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 20;
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);

    #define task "application"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    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
*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2640 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 4 ms 2384 KB Output is correct
4 Correct 3 ms 2384 KB Output is correct
5 Correct 3 ms 2384 KB Output is correct
6 Correct 3 ms 2384 KB Output is correct
7 Correct 3 ms 2384 KB Output is correct
8 Correct 3 ms 2384 KB Output is correct
9 Correct 232 ms 5200 KB Output is correct
10 Correct 248 ms 4688 KB Output is correct
11 Correct 144 ms 4600 KB Output is correct
12 Correct 247 ms 5176 KB Output is correct
13 Correct 149 ms 4876 KB Output is correct
14 Correct 203 ms 3292 KB Output is correct
15 Correct 191 ms 4432 KB Output is correct
16 Correct 163 ms 4688 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1550 ms 2720 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 1550 ms 2720 KB Time limit exceeded
2 Halted 0 ms 0 KB -