113092024-08-08 01:11:52kukkermanMaximális szorzat (50 pont)cpp17Runtime error 40/5067ms2020 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>

void beolvas(std::istream &be, std::vector<int64_t> &v, int &k, int &b) {
    int n;
    be >> n >> k >> b;

    v.resize(n);
    for (auto &x : v) {
        be >> x;
    }
}

void feldolgoz(std::vector<int64_t> &v, int k, int negativ) {
    using std::cout;
    
    static const int64_t M = 1000000007;
    const auto n = static_cast<int>(v.size());

    sort(v.begin(), v.end());

    // Megkeressuk az elso nemnegativ szam poziciojat
    auto p = static_cast<int>(lower_bound(v.begin(), v.end(), 0) - v.begin());

    // Ha a feltetel tobb negativ szamot kovetel meg, mint ahany
    // eredetileg a sorozatban talalhato, akkor nincs megoldas.
    if (p < negativ) {
        cout << "-1\n";
        return;
    }

    // A 0-hoz legkozelebb eso negativ szamtol kezdve megprobalunk annyit
    // 0-ig novelni, hogy hogy pontosan az eloirt darabszamu maradjon.
    for (; p > negativ && k >= 0; p--) {
        // Levonjuk 'k'-bol az aktualis negativ szam 0-ig novelesenek koltseget.
        k += static_cast<int>(v[p - 1]);
        v[p - 1] = 0;
    }

    // Ha nincs elegendo valasztasunk ahhoz, hogy "eltuntessuk" a megfelelo darabszamu
    // negativ szamot, akkor nincs megoldas.
    if (k < 0) {
        cout << "-1\n";
    }

    // Az 's' valtozoban fog eloallni a modositott sorozat elemeinek a szorzata
    int64_t s = 1;

    // Csak abban az esetben kezdjuk el novelni az egyes elemeket, ha van legalabb
    // egy nemnegativ.
    if (p < n) {
        // Kiszamitjuk az elso nemnegativ szamtol kezdodoen egeszen a sorozat vegeig
        // az egyes elemek osszeget:
        // ps[i] = az elso 'i' db. elem osszege az elso nemnegativ szamtol kezdodoen
        std::vector<int64_t> ps(n - p + 1);
        for (int i = p; i < n; i++) {
            ps[i - p + 1] = ps[i - p] + v[i] - v[p];
        }

        // Binaris kereses segitsegevel megkeressuk az elso olyan elem poziciojat,
        // amennyire mar eppen nem potolhatok ki a sorozat elemei az elso nemnegativ
        // elemtol kezdodoen. Pl.:
        // 
        // Legyen v = { -2, -1, 1, 3, 4 }, k = 3
        // 
        // Az elso nemnegativ elem pozicioja (p = 2). 2 db. valasztassal a sorozat
        // kipotolhato egeszen a 3. pozicioig: v = { -2, -1, 1 + 2, 3, 4 },
        // azonban ahhoz, hogy a 4. pozicioig kipotoljuk a sorozatot 4 valasztasra
        // lenne szukseg: v = { -2, -1, 1 + 3, 3 + 1, 4 }, azaz a 4. az elso olyan
        // pozicio, ameddig mar eppen nem potolhato ki 'k' db. valasztasbol.
        int b = p, e = n;
        while (b < e) {
            const auto m = b + (e - b) / 2;
            // A 'p'-edik elemtol az 'm'-edik elemig 'v[m]'-re valo kipotlasanak
            // koltsege.
            const auto x = (v[m] - v[p]) * (m - p + 1) - ps[m - p + 1];

            if (k < x) {
                e = m;
            } else {
                b = m + 1;
            }
        }

        // Levonunk 'k'-bol annyit, amennyi elegendo az elemek kipotoloasahoz
        // a 'p'-ediktol, az 'e-1'-edikig 'v[e-1]'-re. 
        k -= static_cast<int>((v[e - 1] - v[p]) * (e - p) - ps[e - p]);

        // Az e = n esetben, azaz amikor a sorozat kipotolhato egeszen az utolso
        // 'n-1'-edik elemig, elofordulhat, hogy 'k' elegendoen nagy ahhoz, hogy
        // akar 1-nel tobbel is novelhetjuk meg az utolso elemet is. Az 'x' erteke
        // egyenlo lesz azzal az ertekkel, amelyre vegul kipotoljuk a sorozatot
        // 'p'-tol 'e-1'-ig.
        const auto x = v[e - 1] + k / (e - p);

        // Elkezdjuk kiszamitani a modositott vektor elemeinek a szorzatat, ugyelve
        // arra, hogy ne tortenjen tulcsordulas a szorzassoran.

        // Osszeszorozzuk a megmaradt negativ elemeket.
        int i;
        for (i = 0; i < p; i++) {
            s = (s * -v[i]) % M;
        }

        // Osszesen 'k % (e - p)' db. olyan elem lesz, amely meg tovabb novelheto
        // eggyel, azaz amelyeknek az erteke igy 'x+1' lesz.
        for (auto j = k % (e - p); j > 0; j--) {
            s = s * (x + 1) % M;
            i++;
        }

        // A maradek elemek erteke 'x' lesz egeszen 'e-1'-ig. 
        for (; i < e; i++) {
            s = s * x % M;
        }

        // A vektor vegen pedig azok az elemek maradnak, amelyeket mar nem lehet
        // kipotolni, mert tolsagosan nagyok.
        for (; i < n; i++) {
            s = s * v[i] % M;
        }

    } else {
        // Amennyiben csak negativ elemek vannak a sorozatban, akkor csupan csak
        // ossze kell szorozni azokat.
        for (int i = 0; i < n; i++) {
            s = (s * -v[i]) % M;
        }
    }

    cout << s << '\n';
}

int main() {
    std::vector<int64_t> v;
    int k, b;
    beolvas(std::cin, v, k, b);

    feldolgoz(v, k, b);

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base40/50
1Accepted0/02ms356 KiB
2Accepted0/03ms356 KiB
3Accepted0/03ms356 KiB
4Accepted0/03ms356 KiB
5Accepted0/06ms528 KiB
6Accepted2/23ms356 KiB
7Accepted2/23ms356 KiB
8Accepted2/23ms504 KiB
9Accepted2/23ms356 KiB
10Accepted2/28ms536 KiB
11Accepted2/259ms1788 KiB
12Accepted1/164ms1892 KiB
13Accepted1/13ms364 KiB
14Accepted1/17ms504 KiB
15Runtime error0/124ms924 KiB
16Accepted1/125ms1016 KiB
17Runtime error0/125ms1144 KiB
18Accepted1/113ms1124 KiB
19Wrong answer0/146ms1132 KiB
20Wrong answer0/134ms1272 KiB
21Wrong answer0/167ms1196 KiB
22Wrong answer0/127ms996 KiB
23Accepted1/167ms1508 KiB
24Accepted1/163ms1852 KiB
25Accepted2/23ms504 KiB
26Accepted2/27ms484 KiB
27Wrong answer0/234ms744 KiB
28Wrong answer0/134ms888 KiB
29Accepted2/226ms760 KiB
30Accepted1/165ms1252 KiB
31Runtime error0/146ms2020 KiB
32Accepted2/23ms504 KiB
33Accepted2/265ms1148 KiB
34Accepted1/165ms1272 KiB
35Accepted2/265ms1400 KiB
36Accepted2/265ms1124 KiB
37Accepted2/265ms1144 KiB
38Accepted2/265ms1212 KiB
39Accepted1/12ms256 KiB