Niitty

#include <iostream>
#include <cmath>
#include <vector>
#include <map>

using namespace std;


struct Point {
    int x;
    int y;
    Point(int _x, int _y){
        x = _x;
        y = _y;
    }
    Point(){
        x = 0;
        y = 0;
    }
};


struct Node {
    Point pos;
    Node(Point _pos){
        pos = _pos;
    }
};


class Branch {
    Node* n;

    int depth;
 
    // Children of this tree
    Branch* first;
    Branch* second;
 
    public:
        Branch(){
            depth = 0;
            n = NULL;
            first = NULL;
            second = NULL;
        }
        Branch(int _depth){
            depth = _depth;
            n = NULL;
            first = NULL;
            second = NULL;
        }

        void insert(Node*);
        vector<Node*> getClosest(Point, unsigned int*, vector<Node*>);
        unsigned int getEuclideanDistance(Point, Point);
};


void Branch::insert(Node* node){
    if(node == NULL) return;

    if (n == NULL){
        n = node;
        return;
    }

    if(depth % 2 == 0){
        if(node->pos.x < n->pos.x){
            if(first == NULL)
                first = new Branch(depth + 1);
            first->insert(node);
        } else{
            if(second == NULL)
                second = new Branch(depth + 1);
            second->insert(node);
        }
    } else {
        if(node->pos.y < n->pos.y){
            if(first == NULL)
                first = new Branch(depth + 1);
            first->insert(node);
        } else{
            if(second == NULL)
                second = new Branch(depth + 1);
            second->insert(node);
        }
    }
}

//When calling this function give attribute point which is the point that you want to get closest elements of
vector<Node*> Branch::getClosest(Point point, unsigned int* best = NULL, vector<Node*> bestPoints = {}){
    if(n == NULL) return bestPoints;
    if(best == NULL){
        unsigned int topBest = 4294967295;
        best = &topBest;
    }

    unsigned int distance = getEuclideanDistance(n->pos, point);
    if(distance == *best) bestPoints.push_back(n);
    if(distance < *best){
        *best = distance;
        bestPoints.clear();
        bestPoints.push_back(n);
    }

    if(depth % 2 == 0){
        if(n->pos.x > point.x){
            if(first != NULL){
                bestPoints = first->getClosest(point, best, bestPoints);
            }
            if(getEuclideanDistance(Point(n->pos.x, point.y), point) <= *best){
                if(second != NULL){
                    bestPoints = second->getClosest(point, best, bestPoints);
                }
            }
        }
        else{
            if(second != NULL){
                bestPoints = second->getClosest(point, best, bestPoints);
            }
            if(getEuclideanDistance(Point(n->pos.x, point.y), point) <= *best){
                if(first != NULL){
                    bestPoints = first->getClosest(point, best, bestPoints);
                }
            }
        }
    } else{
        if(n->pos.y > point.y){
            if(first != NULL){
                bestPoints = first->getClosest(point, best, bestPoints);
            }
            if(getEuclideanDistance(Point(point.x, n->pos.y), point) <= *best){
                if(second != NULL){
                    bestPoints = second->getClosest(point, best, bestPoints);
                }
            }
        }
        else{
            if(second != NULL){
                bestPoints = second->getClosest(point, best, bestPoints);
            }
            if(getEuclideanDistance(Point(point.x, n->pos.y), point) <= *best){
                if(first != NULL){
                    bestPoints = first->getClosest(point, best, bestPoints);
                }
            }
        }
    }

    return bestPoints;
}


//This function does not return the correct answer since it does not sqrt the answer because I don't want to deal with doubles
unsigned int Branch::getEuclideanDistance(Point pointA, Point pointB){
    return pow(pointA.x - pointB.x, 2) + pow(pointA.y - pointB.y, 2);
}


int binomialCoefficients(int n, int k) {
   if (k == 0 || k == n)
   return 1;
   return binomialCoefficients(n - 1, k - 1) + binomialCoefficients(n - 1, k);
}


struct Pen{
    Point bottomLeft, topRight;
    public:
        Pen(){
            bottomLeft = Point(0, 0);
            topRight = Point(0, 0);
        }
        Pen(Point _bottomLeft, Point _topRight){
            bottomLeft = _bottomLeft;
            topRight = _topRight;
        }
};


bool doesContainDuplicatesOrOverlaps(vector<Pen>*allPens, Pen pen) {
    //cout << "*****" << endl << endl;
    auto endPoint = allPens->end(); 
    for(auto i = allPens->begin(); i != endPoint; i++){
        //cout << i->topRight.x << " " << i->topRight.y << " " << i->bottomLeft.x << " "  << i->bottomLeft.y << endl;
        //cout << pen.topRight.x << " " << pen.topRight.y << " " << pen.bottomLeft.x << " "  << pen.bottomLeft.y << endl << endl;
        if(i->topRight.y >= pen.topRight.y && i->topRight.x <= pen.topRight.x && i->bottomLeft.x >= pen.bottomLeft.x && i->bottomLeft.y <= pen.bottomLeft.y) return true;
        if(i->topRight.y <= pen.topRight.y && i->topRight.x >= pen.topRight.x && i->bottomLeft.x <= pen.bottomLeft.x && i->bottomLeft.y >= pen.bottomLeft.y){
            allPens->erase(i);
            return doesContainDuplicatesOrOverlaps(allPens, pen);
        }
        if(i->bottomLeft.x == pen.bottomLeft.x && i->bottomLeft.y == pen.bottomLeft.y && i->topRight.x == pen.topRight.x && i->topRight.y == pen.topRight.y) return true;
    }

    return false;
}

//If hitting a wall x will be 1 if hitting roof or the floor y will be 1
Point hittingAWall(int roomSize, Pen pen){
    Point point;

    if(pen.topRight.x == roomSize - 1 || pen.bottomLeft.x == 0) point.x = 1;
    if(pen.topRight.y == 0 || pen.bottomLeft.y == roomSize - 1) point.y = 1;

    return point;
}


bool insideWall(vector<Pen>* pens, Pen overlapse){
    for(Pen pen : *pens){
        if(pen.topRight.x <= overlapse.topRight.x && overlapse.bottomLeft.x <= pen.bottomLeft.x && overlapse.topRight.y <= pen.topRight.y && pen.bottomLeft.y <= overlapse.bottomLeft.y){
            int w = pen.topRight.x - pen.bottomLeft.x + 1;
            int h = pen.bottomLeft.y - pen.topRight.y + 1;

            int w2 = overlapse.topRight.x - overlapse.bottomLeft.x + 1;
            int h2 = overlapse.bottomLeft.y - overlapse.topRight.y + 1;

            if(w+h == w2+h2) return true;

            if(w + h <= w2 + h2 - 2) {
                return true;
            };
        }
    }

    return false;
}


int main(){
    int n = 0;
    cin >> n;

    map<char, int> flowerCount;
    map<char, Branch> flowerPositionsTree;
    map<char, vector<Point>> flowerPositions;

    for(int i = 0; i < n; i++){
        string row;
        cin >> row;

        for(int x = 0; (long unsigned int)x < row.size(); x++){
            char flower = row[x];

            flowerCount[flower] += 1;
            flowerPositions[flower].push_back(Point(x, i));
            flowerPositionsTree[flower].insert(new Node(Point(x, i)));
        }
    }

    if(flowerCount.size() == 1){
        cout << pow(binomialCoefficients(n + 1, 2), 2);
        return 0;
    }

    char smallestFlowerChar;
    int smallestFlowerCount = 0;
    for(auto flower : flowerCount){
        if(!smallestFlowerCount || flower.second < smallestFlowerCount){
            smallestFlowerChar = flower.first;
            smallestFlowerCount = flower.second;
        }
    }

    vector<Pen> allPens = {};

    for(Point point : flowerPositions[smallestFlowerChar]){
        vector<Pen> pens = {};
        pens.push_back(Pen(point, point));
        for(auto currentFlower : flowerCount){
            if(currentFlower.first == smallestFlowerChar) continue;
            
            vector<Pen> newPens = {};
            
            vector<Node*> closestCurrentFlowers = flowerPositionsTree[currentFlower.first].getClosest(point);
            for(Node* node : closestCurrentFlowers){
                for(Pen pen : pens){
                    Pen newPen = pen;

                    if(node->pos.x > pen.topRight.x) newPen.topRight.x = node->pos.x;
                    if(node->pos.x < pen.bottomLeft.x) newPen.bottomLeft.x = node->pos.x;
                    if(node->pos.y < pen.topRight.y) newPen.topRight.y = node->pos.y;
                    if(node->pos.y > pen.bottomLeft.y) newPen.bottomLeft.y = node->pos.y;

                    if(!doesContainDuplicatesOrOverlaps(&newPens, newPen)){
                        newPens.push_back(newPen);
                    }
                }
            }

            pens = newPens;
        }

        allPens.insert(allPens.end(), pens.begin(), pens.end());
    }

    /*for(Pen pen : allPens){
        cout << pen.topRight.x << " " << pen.topRight.y << " " << pen.bottomLeft.x << " "  << pen.bottomLeft.y << endl;
    }*/

    long long possiblePens = 0;

    for(auto i = allPens.begin(); i != allPens.end(); i++){
        int w = i->topRight.x - i->bottomLeft.x + 1;
        int h = i->bottomLeft.y - i->topRight.y + 1;

        Point collisions = hittingAWall(n, *i);

        if(n-w == 1) collisions.x = 0;
        if(n-h == 1) collisions.y = 0;

        possiblePens += abs((n-w) * 2 - collisions.x) * abs((n-h) * 2 - collisions.y);
        Pen pen = *i;
        vector<Pen> usedPens = {};
        for(auto x = allPens.rbegin() + distance(i, allPens.end()); x != allPens.rend(); x++){
            if(pen.topRight.y > x->topRight.y) pen.topRight.y = x->topRight.y;
            if(pen.topRight.x < x->topRight.x) pen.topRight.x = x->topRight.x;
            if(pen.bottomLeft.x > x->bottomLeft.x) pen.bottomLeft.x = x->bottomLeft.x;
            if(pen.bottomLeft.y < x->bottomLeft.y) pen.bottomLeft.y = x->bottomLeft.y;

            if(insideWall(&usedPens, pen)) continue;

            usedPens.push_back(pen);

            w = pen.topRight.x - pen.bottomLeft.x + 1;
            h = pen.bottomLeft.y - pen.topRight.y + 1;

            collisions = hittingAWall(n, pen);

            if(n-w == 1) collisions.x = 0;
            if(n-h == 1) collisions.y = 0;

            possiblePens -= abs((n-w) * 2 - collisions.x) * abs((n-h) * 2 - collisions.y);
            //cout << abs((n-w) * 2 - collisions.x) * abs((n-h) * 2 - collisions.y) * multiplier<< endl;
        }
    }

    cout << possiblePens;

    return 0;
}

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 7

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 9

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 10

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 12

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 13

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 14

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 15

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 16

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 17

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 18

Group: 5, 6

Verdict: WRONG ANSWER

Test 19

Group: 5, 6

Verdict: WRONG ANSWER

Test 20

Group: 5, 6

Verdict: WRONG ANSWER

Test 21

Group: 5, 6

Verdict: WRONG ANSWER

Test 22

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 6

Verdict: WRONG ANSWER

Test 24

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 6

Verdict: TIME LIMIT EXCEEDED