oj.uz

Submission #554892

# Submission time Handle Problem Language Result Execution time Memory
554892 2022-04-29T14:29:49 Z PagodePaiva Just Long Neckties (JOI20_ho_t1) C++14
0 / 100
 0 ms 340 KB 
#include<bits/stdc++.h>
#define ms(v) memset(v, -1, sizeof v)
#define pb push_back
#define mp make_pair
#define N 200100
using namespace std;

int n;
int a[N], b[N];
vector <int> savea;
int dif[N], dif1[N];

int busca(int x)
{
    int ini = 0, fim = n;
    int ans = -1; // resposta da pergunta, que inicialmente será -1

    while (ini <= fim)
    {
        int mid = (ini+fim)/2; // meio do intervalo

        if (a[mid] >= x)
        {
            ans = a[mid]; // possível resposta
            fim = mid-1; // reduzo o intervalo para a metade esquerda
        }
        else ini = mid+1; // reduzo o intervalo para a metade direita, já que V[mid] < x
    }
    return ini;

}

int maxdif[N];
int maxdif1[N];

int solve(int id){

    int rem = busca(a[id]);
    if(rem == 0) return maxdif1[1];
    if(rem == n-1) return maxdif[n-2];

    return max(maxdif[rem-1], maxdif1[rem+1]);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n;

    for(int i = 0;i <= n;i++){
        cin >> a[i]; savea.pb(a[i]);
    }

    for(int i = 0;i <= n-1;i++){
        cin >> b[i];
    }

    sort(a, a + n + 1);
    sort(b, b + n);

    for(int i = 0;i < n;i++)dif[i] = max(a[i] - b[i], 0);
    for(int i = 0;i < n;i++){
        dif1[i] = max(a[i+1]- b[i], 0);
        cout << a[i+1] << " " << b[i] << "\n";
    }

    maxdif[0] = dif[0];
    maxdif1[n-1] = dif1[n-1];
    for(int i =1;i < n;i++){
        maxdif[i] = max(maxdif[i-1], dif[i]);
    }

    for(int i = n-2;i >= 0;i--){
        maxdif1[i] = max(maxdif1[i+1], dif1[i]);
    }

    for(int i = 0;i <= n;i++) cout << solve(i) << " ";

    cout << "\n";
    return 0;
}

Compilation message

ho_t1.cpp: In function 'int busca(int)':
ho_t1.cpp:16:9: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   16 |     int ans = -1; // resposta da pergunta, que inicialmente será -1
      |         ^~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 91.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -