Cod sursa(job #2377933)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 11 martie 2019 14:26:08
Problema Aria Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.63 kb
#include <fstream>
#include <iostream>
using namespace std;

ifstream fin("rufe.in");
ofstream fout("rufe.out");

#define Inf 1LL * 0x3FFFFFFFFFFFFFFF

int64_t n, m, a, b, k, i, maxi, crtStep, nxtCol, nxtAdd, crtElems, crtIncrement, toAdd, addedVals, markedA, markedB, mmA, mmB;
int64_t d[5], addedStep[5], adj[5][5];
bool sol;

int64_t crtExpansion(int64_t x) {
    if (addedStep[x] == -1)
        return -Inf;
    return crtStep - addedStep[x];
}

int64_t twoCollide(int a, int b) {
    if (adj[a][b]) return Inf;

    if ((a == 1 && b == 2) || (a == 3 && b == 4)) {
        return m - crtExpansion(a) - crtExpansion(b);
    } else {
        return n - crtExpansion(a) - crtExpansion(b);
    }
}

int64_t minV(int64_t a, int64_t b){
    if (a < 0 && b < 0)
        return Inf;
    else if (a < 0)
        return b;
    else if (b < 0)
        return a;
    else if (a < b)
        return a;
    else
        return b;
}

int64_t diffToNeighbour(int64_t x) {
    if (x == 1) {
        if (twoCollide(1,2) < twoCollide(1,3)) {
            markedA = 1; markedB = 2;
        } else {
            markedA = 1; markedB = 3;
        }
        return minV(twoCollide(1, 2) , twoCollide(1, 3));
    }

    if (x == 2) {
        if (twoCollide(2,1) < twoCollide(2,4)) {
            markedA = 2; markedB = 1;
        } else {
            markedA = 2; markedB = 4;
        }
        return minV(twoCollide(2, 1), twoCollide(2, 4));
    }
    if (x == 3) {
        if (twoCollide(1,3) < twoCollide(3,4)) {
            markedA = 1; markedB = 3;
        } else {
            markedA = 3; markedB = 4;
        }
        return minV(twoCollide(1, 3), twoCollide(3, 4));
    }

    if (twoCollide(2, 4) < twoCollide(3, 4)) {
        markedA = 2; markedB = 4;
    } else {
        markedA = 3; markedB = 4;
    }
    return minV(twoCollide(2, 4), twoCollide(3, 4));
}

int64_t getNextCollisionDistance() {
    int64_t mini = Inf;
    if (addedVals < 2)
        return Inf;
    for (i = 1 ; i <= 4 ; i++) {
        if (addedStep[i] != -1) {
            if (diffToNeighbour(i) / 2LL < mini) {
                mmA = markedA;
                mmB = markedB;
            }
            mini = minV(mini, diffToNeighbour(i) / 2LL);
        }

    }
    return mini;
}

int64_t getNextAddDistance() {
    int64_t mini = Inf;
    toAdd = 0;
    for (i = 1 ; i <= 4 ; i++) {
        if (addedStep[i] == -1) {
            if (d[maxi] - crtStep - d[i] < mini) {
                mini = d[maxi] - crtStep - d[i];
                toAdd = i;
            }
        }
    }
    return mini;
}

int64_t sumAP(int n, int a, int r) {
    return (2 * a + (n - 1) * r) * n / 2;
}

int64_t binSrch(int k, int nxtCol) {
    int64_t ls = 1, ld = nxtCol, mij, tot;
    while (ls <= ld) {
        mij = (ls + ld) / 2;
        tot = sumAP(mij, crtElems + crtIncrement, crtIncrement);
        if (k < tot) {
            ld = mij - 1;
        } else if (k > tot) {
            ls = mij + 1;
        } else {
            return mij;
        }
    }

    return mij;
}

int main()
{
    fin >> n >> m >> a >> b >> k;
    d[1] = (a - 1) + (b - 1);
    d[2] = (a - 1) + (m - b);
    d[3] = (n - a) + (b - 1);
    d[4] = (n - a) + (m - b);
    for (i = 1 ; i <= 4 ; i++) {
        addedStep[i] = -1;
        if (d[i] > d[maxi])
            maxi = i;
    }
    addedVals = 1;
    addedStep[maxi] = 0;
    crtStep = 0;

    sol = false;
    crtIncrement = 1;
    crtElems = 0;
    while (!sol) {
        nxtCol = getNextCollisionDistance();
        nxtAdd = getNextAddDistance();

        if (nxtCol < nxtAdd) { /// Collision happens
            adj[mmA][mmB] = adj[mmB][mmA] = 1;
            if (k <= sumAP(nxtCol, crtElems + crtIncrement, crtIncrement)) {
                fout << d[maxi] - (crtStep + binSrch(k, nxtCol)) + 1;
                return 0;
            } else {
                k -= sumAP(nxtCol, crtElems + crtIncrement, crtIncrement);
                crtStep += nxtCol;
            }

            crtElems += nxtCol * crtIncrement;
            crtIncrement--;
        } else { /// Adding happens ?maybe treat simultaneous case
            if (k <= sumAP(nxtAdd, crtElems + crtIncrement, crtIncrement)) {
                fout << d[maxi] - (crtStep + binSrch(k, nxtAdd)) + 1;
                return 0;
            } else {
                k -= sumAP(nxtAdd, crtElems + crtIncrement, crtIncrement);
                crtStep += nxtAdd;
            }

            addedVals++;
            addedStep[toAdd] = crtStep;
            crtElems += nxtAdd * crtIncrement;
            crtIncrement++;
        }
    }

}