CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:MikaelE
Submission time:2024-11-10 17:46:56 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.00 s1, 2, 3, 4, 5, 6details
#20.00 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#40.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#60.00 s2, 3, 4, 5, 6details
#70.00 s2, 3, 4, 5, 6details
#8ACCEPTED0.00 s2, 3, 4, 5, 6details
#90.00 s2, 3, 4, 5, 6details
#100.01 s3, 4, 5, 6details
#110.01 s3, 4, 5, 6details
#120.01 s3, 4, 5, 6details
#130.01 s3, 4, 5, 6details
#140.02 s4, 5, 6details
#150.01 s4, 5, 6details
#160.01 s4, 5, 6details
#170.01 s4, 5, 6details
#180.10 s5, 6details
#190.07 s5, 6details
#200.10 s5, 6details
#210.09 s5, 6details
#22--6details
#230.83 s6details
#24--6details
#25--6details

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 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 details

Test 1

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

Verdict:

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
0

Test 2

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

Verdict:

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:

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:

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
0

Test 7

Group: 2, 3, 4, 5, 6

Verdict:

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:

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
0

Test 10

Group: 3, 4, 5, 6

Verdict:

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
0

Test 11

Group: 3, 4, 5, 6

Verdict:

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
0

Test 12

Group: 3, 4, 5, 6

Verdict:

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
1.62562e+06

Test 13

Group: 3, 4, 5, 6

Verdict:

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
0

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
37830

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
0

Test 16

Group: 4, 5, 6

Verdict:

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
2.55025e+07

Test 17

Group: 4, 5, 6

Verdict:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
0

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
169060

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
0

Test 20

Group: 5, 6

Verdict:

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
4.0401e+08

Test 21

Group: 5, 6

Verdict:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
0

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
(empty)

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
0

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
15687562500

user output
(empty)

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
(empty)