Submission #1229831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229831		lohacho	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	30 / 100	5090 ms	7476 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int INF = 1e9 + 100;

int n, piv, ans = INF;
array<int, 2> a[600600];
int b[600600], c[600600];

int calc(int x){
    int up = 0, down = 0;

    for (int i=1,j=1,k=1;i<=n*2;i++){
        if ((piv + x <= a[i][1] && a[i][1] < piv + x + n) || a[i][1] < piv + x - n){
            up = max(up, b[j]-a[i][0]);
            down = max(down, a[i][0]-b[j]);
            j++;
        }

        else{
            up = max(up, a[i][0]-c[k]);
            down = max(down, c[k]-a[i][0]);
            k++;
        }
    }

    ans = min(ans, max(up, down));
    return max(up, down);
}

int main(){
    scanf("%d", &n);

    for (int i=1;i<=n*2;i++){
        scanf("%d", &a[i][0]);
        a[i][1] = i;
    } 

    for (int i=1;i<=n;i++) scanf("%d", b+i);
    for (int i=1;i<=n;i++) scanf("%d", c+i);

    piv = 2;
    while(a[piv] < a[piv+n]) piv++;

    sort(a+1, a+n*2+1);
    sort(b+1, b+n+1);
    sort(c+1, c+n+1);

	int mov = 1;
    int l = 0, r = n-1, cnt = 0;
    while(l + 10 <=r && ++cnt < 1000){
        int m1 = (l + l + r) / 3;
		int m2 = (l + r + r) / 3;
        if (calc(m1) > calc(m2)) l = m1+1;
        else if(calc(m1) < calc(m2)) r = m2 - 1;
		else{
			calc(l), calc(r);
			l += mov, r -= mov;
		}
    }
	for(int i = l; i <= min(r, l + 10); ++i){
		calc(i);
	}
	for(int i = max(l, r - 10); i <= r; ++i){
		calc(i);
	}

    for (int i=1;i<=n;i++) swap(b[i], c[i]);
    
    l = 0, r = n-1, cnt = 0;
    while(l + 10 <=r && ++cnt < 1000){
        int m1 = (l + l + r) / 3;
		int m2 = (l + r + r) / 3;
        if (calc(m1) > calc(m2)) l = m1+1;
        else if(calc(m1) < calc(m2)) r = m2 - 1;
		else{
			calc(l), calc(r);
			l += mov, r -= mov;
		}
    }
	for(int i = l; i <= min(r, l + 10); ++i){
		calc(i);
	}
	for(int i = max(l, r - 10); i <= r; ++i){
		calc(i);
	}

    printf("%d\n", ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d", &a[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:41:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     for (int i=1;i<=n;i++) scanf("%d", b+i);
      |                            ~~~~~^~~~~~~~~~~
Main.cpp:42:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     for (int i=1;i<=n;i++) scanf("%d", c+i);
      |                            ~~~~~^~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 0 / 37
• Subtask 5: 0 / 33