CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:asonnine
Submission time:2024-10-29 21:21:47 +0200
Language:C++ (C++17)
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
#30.00 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#50.00 s1, 2, 3, 4, 5, 6details
#60.00 s2, 3, 4, 5, 6details
#70.00 s2, 3, 4, 5, 6details
#80.00 s2, 3, 4, 5, 6details
#90.00 s2, 3, 4, 5, 6details
#100.00 s3, 4, 5, 6details
#110.00 s3, 4, 5, 6details
#120.00 s3, 4, 5, 6details
#130.01 s3, 4, 5, 6details
#140.00 s4, 5, 6details
#150.00 s4, 5, 6details
#160.00 s4, 5, 6details
#170.00 s4, 5, 6details
#180.01 s5, 6details
#190.01 s5, 6details
#200.01 s5, 6details
#210.01 s5, 6details
#220.01 s6details
#230.01 s6details
#240.01 s6details
#250.21 s6details

Code

#include <bits/stdc++.h>
#include <vector>
using namespace std;

int char_to_int(char in) {
	return (int)in - 65;
}

int recurseh(int n, int x, int dx, vector<string> &field, vector<int> species, vector<vector<bool>> &used) {
	int out = 0;
	
	if(used[x+1][dx-1]) {
		used[x+1][dx-1] = false;
		bool left = true;
		vector<int> new_species = species;
		for (int i = 0; i < n; i++) {
			if(new_species[char_to_int(field[i][x])] != 1) {
				new_species[char_to_int(field[i][x])]--;
			} else {
				left = false;
				break;
			}
		}
		if (left) {
			out++;
			out += recurseh(n, x+1, dx-1, field, new_species, used);
		}
	}

	if(used[x][dx-1]) {
		used[x][dx-1] = false;
		bool right = true;
		vector<int> new_species = species;
		for (int i = 0; i < n; i++) {
			if(new_species[char_to_int(field[i][x+dx])] != 1) {
				new_species[char_to_int(field[i][x+dx])]--;
			} else {
				right = false;
				break;
			}
		}
		if (right) {
			out++;
			out += recurseh(n, x, dx-1, field, new_species, used);
		}
	}
	return out;
}

int recursev(int n, int y, int dy, vector<string> &field, vector<int> species, vector<vector<bool>> &used) {
	int out = 0;
	
	if(used[y+1][dy-1]) {
		used[y+1][dy-1] = false;
		bool up = true;
		vector<int> new_species = species;
		for (int i = 0; i < n; i++) {
			if(new_species[char_to_int(field[y][i])] != 1) {
				new_species[char_to_int(field[y][i])]--;
			} else {
				up = false;
				break;
			}
		}
		if (up) {
			out++;
			out += recursev(n, y+1, dy-1, field, new_species, used);
		}
	}
	
	if(used[y][dy-1]) {
		used[y][dy-1] = false;
		bool down = true;
		vector<int> new_species = species;
		for (int i = 0; i < n; i++) {
			if(new_species[char_to_int(field[y+dy][i])] != 1) {
				new_species[char_to_int(field[y+dy][i])]--;
			} else {
				down = false;
				break;
			}
		}
		if (down) {
			out++;
			out += recursev(n, y, dy-1, field, new_species, used);
		}
	}
	
	return out;
}

int main() {
	int n;
	cin >> n;
	vector<string> field(n);
	vector<int> species(26);
	for (int i = 0; i < n; i++) {
		cin >> field[i];
	}
	for (auto i : field) {
		for (auto j : i) {
			species[char_to_int(j)]++;
		}
	}
	vector<vector<bool>> used(n);
	vector<bool> temp(n);
	fill(temp.begin(), temp.end(), true);
	fill(used.begin(), used.end(), temp);
	int h = recurseh(n, 0, n-1, field, species, used)+1;
	fill(temp.begin(), temp.end(), true);
	fill(used.begin(), used.end(), temp);
	int v = recursev(n, 0, n-1, field, species, used)+1;
	cout << h*v << "\n";
}

Test details

Test 1

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

Verdict:

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
(empty)

Test 2

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

Verdict:

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...

correct output
9

user output
12

Test 3

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

Verdict:

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
(empty)

Test 4

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

Verdict: ACCEPTED

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...

correct output
12

user output
12

Test 5

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

Verdict:

input
1
X

correct output
1

user output
(empty)

Test 6

Group: 2, 3, 4, 5, 6

Verdict:

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
(empty)

Test 7

Group: 2, 3, 4, 5, 6

Verdict:

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
15006

Test 8

Group: 2, 3, 4, 5, 6

Verdict:

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
(empty)

Test 9

Group: 2, 3, 4, 5, 6

Verdict:

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
24

Test 10

Group: 3, 4, 5, 6

Verdict:

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
(empty)

Test 11

Group: 3, 4, 5, 6

Verdict:

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
1428000

Test 12

Group: 3, 4, 5, 6

Verdict:

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
(empty)

Test 13

Group: 3, 4, 5, 6

Verdict:

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
3024

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
(empty)

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
(empty)

Test 16

Group: 4, 5, 6

Verdict:

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
(empty)

Test 17

Group: 4, 5, 6

Verdict:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
49164

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
(empty)

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
(empty)

Test 20

Group: 5, 6

Verdict:

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
(empty)

Test 21

Group: 5, 6

Verdict:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
37547900

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
(empty)

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
1848195568