Kortit II

#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(Point _bottomLeft, Point _topRight){
            bottomLeft = _bottomLeft;
            topRight = _topRight;
        }
};


bool doesContainDuplicatesOrOverlaps(vector<Pen>*allPens, Pen pen) {
    for(auto i = allPens->begin(); i != allPens->end(); i++){
        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);
        }
        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;
}


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());
    }

    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;
        possiblePens += (n-w) * (n-h + 1) + (n-h) + 1;
        for(auto x = allPens.begin(); x != i; x++){
            Pen pen = *i;
            
            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;

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

            possiblePens -= (n-w) * (n-h + 1) + (n-h) + 1;
        }
    }

    cout << possiblePens;

    return 0;
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 2

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 5

Verdict: WRONG ANSWER

Test 6

Group: 5

Verdict: WRONG ANSWER