TopCoder Open 2014 MM Round2

RectanglesAndHoles.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdarg>
#include <set>
#include <ctime>
#include <cstring>

using namespace std;

void log(const char *s, ...)
{
    va_list v;
    va_start(v, s);

    vfprintf(stderr, s, v);
    fflush(stderr);

    va_end(v);
}

const int MAX_N = 1024;

int N;
int A[MAX_N], B[MAX_N];
int X[MAX_N], Y[MAX_N], D[MAX_N];
bool U[MAX_N];

int width(int p) { return D[p]==0 ? A[p] : B[p]; }
int height(int p) { return D[p]==0 ? B[p] : A[p]; }

unsigned int xor128(void){
    static unsigned int x=123456789, y=362436069, z=521288629, w=88675123;
    unsigned int t=x^(x<<11); x=y; y=z; z=w;
    return w=(w^(w>>19))^(t^(t>>8));
}

bool overlap(int a1, int a2, int b1, int b2)
{
    return max(a1, b1) < min(a2, b2);
}

bool overlap(int p1, int p2)
{
    return overlap(
        X[p1], X[p1] + width(p1),
        X[p2], X[p2] + width(p2)) &&
    overlap(
        Y[p1], Y[p1] + height(p1),
        Y[p2], Y[p2] + height(p2));
}

bool overlap(int p)
{
    for (int i=0; i<N; i++)
        if (i!=p && U[i] && overlap(p, i))
            return true;
    return false;
}

void put(int p)
{
    while (true)
    {
        D[p] = xor128()%2;

        int C[MAX_N];
        int cn = 0;
        for (int i=0; i<N; i++)
        if (U[i])
            C[cn++] = i;;
        int o = C[xor128()%cn];

        int CX[8];
        int CY[8];
        cn = 0;
        
        for (int yi=0; yi<2; yi++)
        {
            int y = yi==0 ? Y[o] - height(p) : Y[o] + height(o);
            int l = X[o] - width(p);
            int r = X[o] + width(o);

            for (int i=0; i<N && l<=r; i++)
            if (U[i] && overlap(Y[i], Y[i]+height(i), y, y+height(p)))
            {
                int dl = X[i]+width(i) - l;
                int dr = r - (X[i]-width(p));
                if (dl<dr)
                    l += max(0, dl);
                else
                    r -= max(0, dr);
            }
        
            if (l<=r)
            {
                CX[cn] = l;
                CY[cn] = y;
                cn++;
                CX[cn] = r;
                CY[cn] = y;
                cn++;
            }
        }

        for (int xi=0; xi<2; xi++)
        {
            int x = xi==0 ? X[o] - width(p) : X[o] + width(o);
            int u = Y[o] - height(p);
            int d = Y[o] + height(o);

            for (int i=0; i<N && u<=d; i++)
            if (U[i] && overlap(X[i], X[i]+width(i), x, x+width(p)))
            {
                int du = Y[i]+height(i) - u;
                int dd = d - (Y[i]-height(p));
                if (du<dd)
                    u += max(0, du);
                else
                    d -= max(0, dd);
            }
        
            if (u<=d)
            {
                CX[cn] = x;
                CY[cn] = u;
                cn++;
                CX[cn] = x;
                CY[cn] = d;
                cn++;
            }
        }

        if (cn > 0)
        {
            int r = xor128()%cn;
            X[p] = CX[r];
            Y[p] = CY[r];
            U[p] = true;
            return;
        }
    }
}

long long score(int *cnt=NULL, long long *area=NULL, bool *T=NULL)
{
    set<int> SX, SY;
    for (int i=0; i<N; i++)
    if (U[i])
    {
        SX.insert(X[i]);
        SX.insert(X[i]+width(i));
        SY.insert(Y[i]);
        SY.insert(Y[i]+height(i));
    }
    SX.insert(-99999999);
    SX.insert(+99999999);
    SY.insert(-99999999);
    SY.insert(+99999999);

    vector<int> VX(SX.begin(), SX.end());
    vector<int> VY(SY.begin(), SY.end());

    int w = SX.size()-1;
    int h = SY.size()-1;
    
    vector<vector<int> > F(h, vector<int>(w, 0));

    for (int i=0; i<N; i++)
    if (U[i])
    {
        int l = int(lower_bound(VX.begin(), VX.end(), X[i]) - VX.begin());
        int r = int(lower_bound(VX.begin(), VX.end(), X[i]+width(i)) - VX.begin());
        int u = int(lower_bound(VY.begin(), VY.end(), Y[i]) - VY.begin());
        int d = int(lower_bound(VY.begin(), VY.end(), Y[i]+height(i)) - VY.begin());
        
        for (int y=u; y<d; y++)
        for (int x=l; x<r; x++)
            F[y][x] = -i-1;
    }

    if (T!=NULL)
        for(int i=0; i<N; i++)
            T[i] = false;

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    int c = 0;
    long long a = 0LL;

    vector<int> QX, QY;

    for (int y=0; y<h; y++)
    for (int x=0; x<w; x++)
    if (F[y][x]==0)
    {
        QX.push_back(x);
        QY.push_back(y);
        c++;

        if (x==0 && y==0)
        {
            while (!QX.empty())
            {
                int px = QX.back(); QX.pop_back();
                int py = QY.back(); QY.pop_back();
                F[py][px] = c;

                for (int d=0; d<4; d++)
                {
                    int tx = px + dx[d];
                    int ty = py + dy[d];
                    if (0<=tx && tx<w && 0<=ty && ty<h && F[ty][tx]==0)
                        QX.push_back(tx),
                        QY.push_back(ty);
                }
            }
        }
        else
        {
            while (!QX.empty())
            {
                int px = QX.back(); QX.pop_back();
                int py = QY.back(); QY.pop_back();
                if (F[py][px] != 0)
                    continue;

                F[py][px] = c;
                a += (long long)(VX[px+1]-VX[px])*(VY[py+1]-VY[py]);

                for (int d=0; d<4; d++)
                {
                    int tx = px + dx[d];
                    int ty = py + dy[d];
                    if (F[ty][tx]==0)
                        QX.push_back(tx),
                        QY.push_back(ty);
                    if (T!=NULL && F[ty][tx]<0)
                        T[-F[ty][tx]-1] = true;
                }
            }
        }
    }
    c--;

    if (cnt != NULL)
        *cnt = c;
    if (area != NULL)
        *area = a;

    return a*c*c;
}

void solve()
{
    for (int i=0; i<N; i++)
    {
        if (i==0)
        {
            X[i] = 0;
            Y[i] = 0;
            D[i] = 0;
            U[i] = true;
            continue;
        }
        else
        {
            put(i);
        }
    }

    bool T[MAX_N];
    long long scr = score(NULL, NULL, T);

    for (int i=0; ; i++)
    {
        if (i%16==0 && clock()>=6*CLOCKS_PER_SEC)
            break;

        int CP[MAX_N*4];
        int cpn = 0;
        for (int j=0; j<N; j++)
            for (int k=0; k<(T[j]?1:4); k++)
                CP[cpn++] = j;
        int p = CP[xor128()%cpn];

        int px = X[p];
        int py = Y[p];
        int pd = D[p];
        bool pT[MAX_N];
        memcpy(pT, T, sizeof(bool)*N);

        put(p);

        int cnt;
        long long area;
        long long s = score(&cnt, &area, T);

        if (s >= scr)
            scr = s;
        else
        {
            X[p] = px;
            Y[p] = py;
            D[p] = pd;
            memcpy(T, pT, sizeof(bool)*N);
        }
    }

    log("Score: %lld\n", scr);
}

class RectanglesAndHoles{public:
vector<int> place(vector<int> A, vector<int> B)
{
    N = (int)A.size();
    for (int i=0; i<N; i++)
    {
        ::A[i] = A[i];
        ::B[i] = B[i];
        X[i] = 0;
        Y[i] = 0;
        D[i] = 0;
        U[i] = false;
    }

    solve();

    vector<int> ret;
    for (int i=0; i<N; i++)
        ret.push_back(X[i]),
        ret.push_back(Y[i]),
        ret.push_back(D[i]);

    log("Time: %f\n", (double)clock()/CLOCKS_PER_SEC);
    return ret;
}};

#ifdef TOPCODER_LOCAL

int main()
{
    int N;
    cin >> N;

    vector<int> A(N);
    for (int i=0; i<N; i++)
        cin >> A[i];
    vector<int> B(N);
    for (int i=0; i<N; i++)
        cin >> B[i];

    RectanglesAndHoles RaH;
    vector<int> ret = RaH.place(A, B);

    for (int i=0; i<3*N; i++)
        cout << ret[i] << endl;

    return 0;
}

#endif