Task: | Niitty |
Sender: | MikaelE |
Submission time: | 2024-11-10 17:46:56 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
#4 | WRONG ANSWER | 0 |
#5 | WRONG ANSWER | 0 |
#6 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.00 s | 1, 2, 3, 4, 5, 6 | details |
#2 | WRONG ANSWER | 0.00 s | 1, 2, 3, 4, 5, 6 | details |
#3 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5, 6 | details |
#4 | WRONG ANSWER | 0.00 s | 1, 2, 3, 4, 5, 6 | details |
#5 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5, 6 | details |
#6 | WRONG ANSWER | 0.00 s | 2, 3, 4, 5, 6 | details |
#7 | WRONG ANSWER | 0.00 s | 2, 3, 4, 5, 6 | details |
#8 | ACCEPTED | 0.00 s | 2, 3, 4, 5, 6 | details |
#9 | WRONG ANSWER | 0.00 s | 2, 3, 4, 5, 6 | details |
#10 | WRONG ANSWER | 0.01 s | 3, 4, 5, 6 | details |
#11 | WRONG ANSWER | 0.01 s | 3, 4, 5, 6 | details |
#12 | WRONG ANSWER | 0.01 s | 3, 4, 5, 6 | details |
#13 | WRONG ANSWER | 0.01 s | 3, 4, 5, 6 | details |
#14 | WRONG ANSWER | 0.02 s | 4, 5, 6 | details |
#15 | WRONG ANSWER | 0.01 s | 4, 5, 6 | details |
#16 | WRONG ANSWER | 0.01 s | 4, 5, 6 | details |
#17 | WRONG ANSWER | 0.01 s | 4, 5, 6 | details |
#18 | WRONG ANSWER | 0.10 s | 5, 6 | details |
#19 | WRONG ANSWER | 0.07 s | 5, 6 | details |
#20 | WRONG ANSWER | 0.10 s | 5, 6 | details |
#21 | WRONG ANSWER | 0.09 s | 5, 6 | details |
#22 | TIME LIMIT EXCEEDED | -- | 6 | details |
#23 | WRONG ANSWER | 0.83 s | 6 | details |
#24 | TIME LIMIT EXCEEDED | -- | 6 | details |
#25 | TIME LIMIT EXCEEDED | -- | 6 | details |
Code
#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 treeBranch* 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 ofvector<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 doublesunsigned 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 1Point 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 details
Test 1
Group: 1, 2, 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
10 TNCTNPNTPC NPPNTNTPTP NTNTTCNTCT NPCPNPPNTT ... |
correct output |
---|
2035 |
user output |
---|
0 |
Test 2
Group: 1, 2, 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
10 NFWQLWNWYS DZOQJVXFPJ CNHXPXMCQD QRTBVNLTQC ... |
correct output |
---|
9 |
user output |
---|
0 |
Test 3
Group: 1, 2, 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
10 XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX ... |
correct output |
---|
3025 |
user output |
---|
3025 |
Test 4
Group: 1, 2, 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
10 FFFFFFFFFF FFFFFCFFFF FFFFFFJFFF FFFFFFFFFF ... |
correct output |
---|
12 |
user output |
---|
0 |
Test 5
Group: 1, 2, 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
1 X |
correct output |
---|
1 |
user output |
---|
1 |
Test 6
Group: 2, 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
20 BBCBUBOUOBBCUUBBCOUO BOUCOOCUBCOOOCOBOCUO UCCUUUOBCOCBCBUBUCOO BUOBUCUCUOOBCOOUBUOO ... |
correct output |
---|
38724 |
user output |
---|
0 |
Test 7
Group: 2, 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
20 CBGLSHGZHYZDWBNDBJUG SMUXOJQYPXZDTMJUIWOJ XIDSTNBGHKRKOVUVMINB MTQGCFRUHQKALXRNCQGS ... |
correct output |
---|
8334 |
user output |
---|
0 |
Test 8
Group: 2, 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
20 KKKKKKKKKKKKKKKKKKKK KKKKKKKKKKKKKKKKKKKK KKKKKKKKKKKKKKKKKKKK KKKKKKKKKKKKKKKKKKKK ... |
correct output |
---|
44100 |
user output |
---|
44100 |
Test 9
Group: 2, 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
20 AAAAAAAAXAAAAAAAAAAA AAAWAAAAAAAAAAAAAOAA AAAAAAAAAAAAAAAAAPAA AAAAAAAAKAAAAAAAAAAZ ... |
correct output |
---|
18 |
user output |
---|
0 |
Test 10
Group: 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
50 GRGREEEGREGXRXXEGXXREXGRRRGRRR... |
correct output |
---|
1584665 |
user output |
---|
0 |
Test 11
Group: 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
50 AITIISJUHCCRZNKSDCNQKYSQRINFWJ... |
correct output |
---|
1077746 |
user output |
---|
0 |
Test 12
Group: 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
50 OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO... |
correct output |
---|
1625625 |
user output |
---|
1.62562e+06 |
Test 13
Group: 3, 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
50 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF... |
correct output |
---|
1680 |
user output |
---|
0 |
Test 14
Group: 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
100 NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM... |
correct output |
---|
25325366 |
user output |
---|
37830 |
Test 15
Group: 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
100 LIMQQIHASECROEVILNVULGWZJPPKOG... |
correct output |
---|
22342463 |
user output |
---|
0 |
Test 16
Group: 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
100 TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT... |
correct output |
---|
25502500 |
user output |
---|
2.55025e+07 |
Test 17
Group: 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
100 QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ... |
correct output |
---|
25650 |
user output |
---|
0 |
Test 18
Group: 5, 6
Verdict: WRONG ANSWER
input |
---|
200 NAANANMMKNKKAKMKMAKNKMNKMMNNAA... |
correct output |
---|
403292767 |
user output |
---|
169060 |
Test 19
Group: 5, 6
Verdict: WRONG ANSWER
input |
---|
200 OMYWATTLURKQPTKEFMGGYAOONXWVSC... |
correct output |
---|
388111321 |
user output |
---|
0 |
Test 20
Group: 5, 6
Verdict: WRONG ANSWER
input |
---|
200 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC... |
correct output |
---|
404010000 |
user output |
---|
4.0401e+08 |
Test 21
Group: 5, 6
Verdict: WRONG ANSWER
input |
---|
200 LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL... |
correct output |
---|
14159445 |
user output |
---|
0 |
Test 22
Group: 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW... |
correct output |
---|
15683003812 |
user output |
---|
(empty) |
Test 23
Group: 6
Verdict: WRONG ANSWER
input |
---|
500 OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE... |
correct output |
---|
15575906951 |
user output |
---|
0 |
Test 24
Group: 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 IIIIIIIIIIIIIIIIIIIIIIIIIIIIII... |
correct output |
---|
15687562500 |
user output |
---|
(empty) |
Test 25
Group: 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW... |
correct output |
---|
3058970930 |
user output |
---|
(empty) |