백준 19825 - Minimal Product

 

 

문제 번역

주어진 정수 배열 $a_1,\dots,a_n$에서, $i<j$이고 $a_i<a_j$인 두 인덱스 $i$와 $j$를 찾아야 합니다. 그리고 이 때 $a_i \cdot a_j$의 곱이 가능한 한 작게 되도록 해야 합니다.

- chat GPT -

 

step 1

$n$이 20000000이기 때문에 $O(n \log n)$도 터집니다

$j$가 정해졌을 때 최적의 $i$를 구할 것입니다. $a_j$가 0 미만인 경우와 이상인 경우로 나누어 봅시다.

• 0 미만인 경우 : $a_i$는 항상 음수입니다. $a_i \cdot a_j$가 작아지려면 $a_i$는 가능한 후보들 중 가장 큰 수가 되어야 합니다. 이 경우 $a_i \cdot a_j$는 항상 양수입니다.
• 0 이상인 경우 : $a_i$가 양수, 음수 여부에 관계없이 가장 작은 값을 선택해야 합니다. 

step 2

$a_i < 0, a_j >= 0$인 경우가 있다고 합시다. 이 경우 정답은 음수이고 $a_j < 0$인 경우는 고려할 필요가 없습니다.

그럼 모든 $a_j >= 0$에 대해서 가장 작은 $a_i$를 구하면 됩니다.

step 3

$a_i < 0, a_j >= 0$인 경우가 없다고 합시다. 이 경우

 

( >=0 인 수들), (<0 인 수들)

 

이런 색으로 배치되어 있습니다. 물론 ( >=0 인 수들)이 없거나 (<0 인 수들)이 없을 수도 있습니다. 이 두 영역은 서로 영향을 미치지 못하므로 따로 계산해 줄 것입니다.

 

( >=0 인 수들)는 위에서 했던 방식으로 진행할 수 있습니다.

 

(<0 인 수들)인 수는 결과가 항상 양수이기 때문에 전부 $-1$을 곱해 줄 것입니다. 다만 이렇게 하면 크기 관계가 반대로 되기 때문에 $i<j$이고 $a_i>a_j$인 수를 찾는 문제로 바뀝니다. 그래서 $-1$ 을 곱한 뒤 전체 영역을 뒤집어 줄 것입니다. 이렇게 하면 ( >=0 인 수들)과 같은 방식으로 계산할 수 있습니다.

주의할 점

$a$를 계산해 주는 과정에서 long long도 터집니다. unsigned long long 을 사용하고 계속 $2^{32}$로 나누어 줘야 계산이 잘 됩니다. 

코드

#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#include <cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
ll b[10000010], pos[10000010];
int main() {
    ll m, i;
    ll n, l, r, x, y, z,dab;
    scanf("%lld", &m);
    while(m--) {
        ll ez = 0;
        scanf("%lld%lld%lld%lld%lld%lld%lld%lld", &n, &l, &r, &x, &y, &z, &b[1], &b[2]);
        for (i = 3;i <= n;i++) {
            b[i] = ((unsigned ll)(b[i - 2]) * x % (1ll << 32)) + ((unsigned ll)b[i - 1] * y % (1ll << 32)) + z;
            b[i] %= (1ll << 32);
        }
        for (i = 1;i <= n;i++) {
            ll t = b[i] % (r - l + 1) + l;
            b[i] = t;
            if (i > 1 && b[i - 1] < 0 && b[i] >= 0) ez=1;
        }

        dab = 9000000000000000000ll;
        if (ez == 1) {
            ll minn = b[1];
            for (i = 2;i <= n;i++) {
                if (minn<b[i] && dab>minn * b[i]) dab = minn * b[i];
                minn = min(minn, b[i]);
            }
        }
        else {
            i = 1;
            if (b[1] >= 0) {
                ll minn = b[1];
                for (i = 2;i <= n;i++) {
                    if (b[i] < 0) break;
                    if (minn<b[i] && dab>minn * b[i]) dab = minn * b[i];
                    minn = min(minn, b[i]);
                }
            }

            ll s = i;
            for (i = s;i <= n;i++) b[i] *= -1;
            ll minn = b[n];
            for (i = n - 1;i >= s;i--) {
                if (minn<b[i] && dab>minn * b[i]) dab = minn * b[i];
                minn = min(minn, b[i]);
            }
        }
        if (dab == 9000000000000000000ll) printf("IMPOSSIBLE\n");
        else printf("%lld\n", dab);
    }
    return 0;
}