oj.uz

Submission #1011303

# Submission time Handle Problem Language Result Execution time Memory
1011303 2024-06-30T10:07:11 Z Pacybwoah Growing Vegetables is Fun 5 (JOI24_vegetables5) C++17
0 / 100
 733 ms 19124 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cmath>
typedef long long ll;
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> vec(2 * n + 1);
    for(int i = 1; i <= 2 * n; i++) cin >> vec[i];
    vector<int> b(n + 1), c(n + 1);
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) cin >> c[i];
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    int l = 0, r = 1e9;
    while(l < r){
        int mid = (l + r) >> 1;
        bool flag = 0;
        for(int t = 0; t < 2; t++){
            vector<bool> pre_good(2 * n + 1), post_good(2 * n + 1);
            for(int i = 1; i <= n; i++){
                if(abs(b[i] - vec[i]) <= mid) pre_good[i] = 1;
                if(i > 1) pre_good[i] = pre_good[i] && pre_good[i - 1];
            }
            for(int i = n + 1; i <= 2 * n; i++){
                if(abs(c[2 * n + 1 - i] - vec[i]) <= mid) pre_good[i] = 1;
                if(i > n + 1) pre_good[i] = pre_good[i] && pre_good[i - 1];
            }
            int lptr = 1, rptr = 0, al, ar;
            vector<int> d(2 * n + 1);
            for(int i = 1; i <= n; i++){
                while(lptr <= n && abs(c[lptr] - vec[i]) > mid) lptr++;
                if(lptr > rptr) rptr = lptr;
                while(rptr < n && abs(c[rptr + 1] - vec[i]) <= mid) rptr++;
                al = i - rptr + 1, ar = i - lptr + 1;
                al = max(1, al);
                ar = min(n, ar);
                if(al > ar) continue;
                d[al]++;
                if(ar < n) d[ar + 1]--;
            }
            for(int i = 1; i <= n; i++) d[i] += d[i - 1];
            for(int i = 1; i <= n; i++) if(d[i] == n - i + 1) post_good[i] = 1;
            lptr = 1, rptr = 0;
            for(int i = 2 * n; i > n; i--){
                while(lptr <= n && abs(b[lptr] - vec[i]) > mid) lptr++;
                if(lptr > rptr) rptr = lptr;
                while(rptr < n && abs(b[rptr + 1] - vec[i]) <= mid) rptr++;
                if(lptr == n + 1) continue;

                al = i + lptr - n, ar = i + rptr - n;
                //cout << i << " " << vec[i] << " " << lptr << " " << rptr << " " << al << " " << ar << "\n";
                al = max(n + 1, al);
                ar = min(2 * n, ar);
                if(al > ar) continue;
                d[al]++;
                if(ar < 2 * n) d[ar + 1]--;
            }
            for(int i = n + 2; i <= 2 * n; i++) d[i] += d[i - 1];
            for(int i = n + 1; i <= 2 * n; i++) if(d[i] == 2 * n - i + 1) post_good[i] = 1;
            for(int i = 1; i < n; i++){
                if(pre_good[i] && pre_good[n + i] && post_good[i + 1] && post_good[n + i + 1]) flag = 1;
            }
            if(pre_good[n] && pre_good[2 * n]) flag = 1;
            swap(b, c);
            //cout << pre_good[1] << " " << pre_good[10] << " " << post_good[2] << " " << post_good[11] << "\n";
        }
        if(flag){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    cout << l << "\n";
}
// g++ pC.cpp -std=c++17 -Wshadow -Wall -fsanitize=undefined -fsanitize=address -o run

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 19124 KB Output is correct
2 Correct 591 ms 15728 KB Output is correct
3 Correct 516 ms 13120 KB Output is correct
4 Incorrect 633 ms 19044 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -