Code Submission Evaluation System Login

Datatähti 2019 alku

Start:2018-10-01 00:00:00
End:2018-10-15 00:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2019 alku - Results
History
2018-10-02 19:33:37100
2018-10-02 17:22:5045
2018-10-02 16:58:4714
2018-10-02 16:55:470
2018-10-02 15:52:1114
2018-10-02 15:28:2231
2018-10-02 15:25:380
2018-10-02 15:00:5714
2018-10-02 15:00:34
2018-10-02 14:01:2914
2018-10-02 13:59:3014
2018-10-02 11:42:5914
2018-10-02 11:42:0614
2018-10-02 11:15:310
Task:Ruudukko
Sender:Olli
Submission time:2018-10-02 19:33:37
Language:C++
Status:READY
Score:100

Feedback

groupverdictscore
#1ACCEPTED31
#2ACCEPTED14
#3ACCEPTED55

Test results

testverdicttime (s)group
#1ACCEPTED0.01 / 1.001details
#2ACCEPTED0.03 / 1.001details
#3ACCEPTED0.02 / 1.001details
#4ACCEPTED0.02 / 1.001details
#5ACCEPTED0.02 / 1.001details
#6ACCEPTED0.02 / 1.001details
#7ACCEPTED0.01 / 1.001details
#8ACCEPTED0.02 / 1.001details
#9ACCEPTED0.02 / 1.001details
#10ACCEPTED0.02 / 1.001details
#11ACCEPTED0.03 / 1.002details
#12ACCEPTED0.03 / 1.002details
#13ACCEPTED0.03 / 1.002details
#14ACCEPTED0.06 / 1.002details
#15ACCEPTED0.07 / 1.002details
#16ACCEPTED0.10 / 1.002details
#17ACCEPTED0.11 / 1.002details
#18ACCEPTED0.12 / 1.002details
#19ACCEPTED0.11 / 1.002details
#20ACCEPTED0.12 / 1.002details
#21ACCEPTED0.13 / 1.003details
#22ACCEPTED0.13 / 1.003details
#23ACCEPTED0.12 / 1.003details
#24ACCEPTED0.13 / 1.003details
#25ACCEPTED0.11 / 1.003details
#26ACCEPTED0.12 / 1.003details
#27ACCEPTED0.12 / 1.003details
#28ACCEPTED0.11 / 1.003details
#29ACCEPTED0.12 / 1.003details
#30ACCEPTED0.12 / 1.003details

Code

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

bool printStuff = false;

typedef long long ll;

const int N = 555;
const int M = 1e9 + 7;

char t[N][N];

ll n;

int aA;
int amB;

void swaR(int a, int b) {
	for(int x = 1; x <= n; ++x) {
		char c = t[a][x];
		char d = t[b][x];
		t[a][x] = d;
		t[b][x] = c;
	}
}

void swaC(int a, int b) {
	for(int y = 1; y <= n; ++y) {
		char c = t[y][a];
		char d = t[y][b];
		t[y][a] = d;
		t[y][b] = c;
	}
}

void print() {

	for(int y = 1; y <= n; ++y) {
		for(int x = 1; x <= n; ++x) {
			cout << t[y][x];
		}
		cout << "\n";
	}
	cout << "\n";
}

void sor() {

	vector<int> broken;

	for(int y = n; y >= n - amB + 1; --y) {
		bool conB = false;
		for(int x = 1; x <= n; ++x) {
			if(t[y][x] == 'B') {
				conB = true;
				break;
			}
		}

		if(!conB) broken.push_back(y);
	}

	for(int y = n - amB; y >= 1; --y) {
		bool conB = false;
		for(int x = 1; x <= n; ++x) {
			if(t[y][x] == 'B') {
				conB = true;
				break;
			}
		}
		if(!conB) {
			continue;
		}
		int k = broken[broken.size() - 1];
		swaR(k, y);
		broken.pop_back();
	}


	for(int y = n; y >= n - amB + 1; --y) {
		int col = -1;
		for(int x = 1; x <= n; ++x) {
			if(t[y][x] == 'B') {
				col = x;
			}
		}
		swaC(n - y + 1, col);
	}

	aA = 0;
	for(int x = amB + 1; x <= n; ++x) {
		for(int y = n - amB; y >= 1; --y) {
			if(t[y][x] == 'A') {
				++aA;
			}
		}
	}

	for(int y = n - amB; y >= n - amB - aA + 1; --y) {
		bool conA = false;
		for(int x = amB + 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				conA = true;
				break;
			}
		}

		if(!conA) {
			broken.push_back(y);
		}
	}

	for(int y = n - amB - aA; y >= 1; --y) {
		bool conA = false;
		for(int x = amB + 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				conA = true;
				break;
			}
		}
		if(conA) {
			int k = broken[broken.size() - 1];
			swaR(k, y);
			broken.pop_back();
		}
	}


	for(int y = n - amB; y >= n - amB - aA + 1; --y) {
		int col = -1;
		for(int x = amB + 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				col = x;
				break;
			}
		}
		swaC(n - y + 1, col);
	}

	if(printStuff) {
		cout << n << "\n";
		print();
	}
}


ll dp[N][N];


void fillDP() {
	dp[0][0] = 1;
	for(int x = 1; x <= n; ++x) {
		dp[x][0] = dp[x-1][0]*x;
		dp[x][0] %= M;
	}

	for(ll y = 1; y <= n; ++y) {
		for(ll x = y; x <= n; ++x) {
			dp[x][y] = dp[x-1][y-1]*(x-y);
			dp[x][y] %= M;
			if(y == 1) continue;
			dp[x][y] += dp[x-1][y-2]*(y-1);
			dp[x][y] %= M;
		}
	}
}

ll exp(ll a, ll e) {
	if(e == 0) return 1;
	if(e%2 == 0)  {
		ll c = exp(a, e/2);
		return (c*c)%M;
	}
	ll c = exp(a, e-1);
	return (c*a)%M;
}

ll fact[N];
ll binom[N][N];

bool marked[N];

int main() {
	cin >> n;
	for(int y = 1; y <= n; ++y) {
		for(int x = 1; x <= n; ++x) {
			char c;
			cin >> c;
			t[y][x] = c;
			if(c == 'B') ++amB;
		}
	}
	sor();

	fillDP();
	fact[0] = 1;
	for(ll i = 1; i <= n; ++i) {
		fact[i] = fact[i-1]*i;
		fact[i] %= M;
	}
	for(int m = 0; m <= n; ++m) {
		for(int k = 0; k <= m; ++k) {
			ll b = fact[m];
			b *= exp(fact[k], M-2);
			b %= M;
			b *= exp(fact[m-k], M-2);
			b %= M;
			binom[m][k] = b;
		}
	}

	ll ans = 0;



	int a1 = 0;
	int a2 = 0;
	int a3 = 0;


	//calculate a2
	for(int y = 1; y <= n - amB - aA; ++y) {
		for(int x = 1; x <= amB; ++x) {
			if(t[y][x] == 'A') {
				++a2;
			}
		}
	}

	//calculate a3;

	for(int y = n - amB; y <= n; ++y) {
		for(int x = amB + aA + 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				++a3;
			}
		}
	}
	//calculate a1;
	for(int x = 1; x <= amB; ++x) {
		for(int y = n - amB + 1; y <= n; ++y) {
			if(t[y][x] == 'A') {
				++a1;

			}
		}
	}
/*
	for(int i = 0; i <= n; ++i) {
		for(int a = 0; a <= i; ++a) {
			cout << dp[i][a] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
*/
	int initialB = 0;
	//How many B:s have been hit initially

	for(int x = 1; x <= amB; ++x) {
		for(int y = 1; y <= n; ++y) {
			if(t[y][x] == 'A') {
				if(!marked[x]) {
					++initialB;
					marked[x] = true;
				}
				if(y >= n - amB + 1) {
					if(!marked[n-y+1]) {
						++initialB;
						marked[n-y+1] = true;
					}
				}
			}

		}
	}
	for(int y = n - amB + 1; y <= n; ++y) {
		for(int x = amB + 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				if(!marked[n - y + 1]) {
					++initialB;
					marked[n-y+1] = true;
				}
			}
		}
	}

	int hitAbove = 0;
	int noHitAbove = 0;
	int hitRight = 0;
	int noHitRight = 0;

	for(int x = 1; x <= amB; ++x) {
		bool contains = false;
		for(int y = 1; y <= n; ++y) {
			if(t[y][x] == 'A') {
				contains = true;
				break;
			}
		}
		if(contains) continue;
		for(int y = 1; y <= n; ++y) {
			if(t[y][x] == 'B') {
				if(marked[x]) {
					++noHitAbove;
				} else {
					++hitAbove;
				}
				break;
			}
		}
	}

	for(int y = n - amB + 1; y <= n; ++y) {
		bool contains = false;
		for(int x = 1; x <= n; ++x) {
			if(t[y][x] == 'A') {
				contains = true;
				break;
			}
		}
		if(contains) continue;
		for(int x = 1; x <= n; ++x) {
			if(t[y][x] == 'B') {
				if(marked[x]) {
					++noHitRight;
				} else {
					++hitRight;
				}
				break;
			}
		}
	}


	for(ll f2 = max(a2, a3); f2 <= min((ll) amB - a1, n - amB - aA); ++f2) {
		for(ll amountOfB = initialB; amountOfB <= amB; ++amountOfB) {
			//We will have amountOfB of B:s that have been hit
			//We have to hit amountOfB - initialB more
			ll A23 = 0;
			int t = amountOfB - initialB;
			if(t > f2 - a2 + f2 - a3) continue;
			int s = n - amB - aA;
			if(s < f2) continue;
			
			if(printStuff) {
				cout << "\n\n";
				cout << "The configuration we have: \n";
				cout << "We have to hit " << t << " more B:s\n";
				cout << "We should add " << f2 - a2 << " and " << f2 - a3 << " new ones \n";
				cout << "There are " << noHitAbove << " and " << noHitRight << " choices that do not hit\n";
				cout << "and " << hitAbove << " and " << hitRight << " choices that hit a new one \n";
			}
			for(int o2 = 0; o2 <= t; ++o2) {
				int d2 = f2 - a2;
				ll A2 = binom[noHitAbove][d2 - o2]*binom[hitAbove][o2];
				A2 %= M;
				A2 *= fact[s - a2];
				A2 %= M;
				A2 *= exp(fact[s - a2 - d2], M-2);
				A2 %= M;


				int o3 = t - o2;
				int d3 = f2 - a3;
				if(o3 > d3) continue;
				if(hitRight < o2) continue;
				ll A3 = binom[hitRight - o2][o3] * binom[noHitRight + o2][d3-o3];
				A3 %= M;
				A3 *= fact[s - a3];
				A3 %= M;
				A3 *= exp(fact[s - a3 - d3], M-2);
				A3 %= M;
				A23 += A2*A3;
				if(printStuff) {
					cout << "So if " << o2 << " " << o3 << " we have " << A2 << " " << A3 << "\n";
					cout << "Because we have " << s - a2 << " and " << s - a3 << " possible depths\n";
					cout << "And difference d3 is " << d3 << "\n";
					cout << binom[hitRight - o2][o3] << " " << binom[noHitRight + o2][d3] << " " << binom[s-a3][d3] << "\n";
					cout << noHitRight << "\n";

				}
				A23 %= M;

			}
			if(printStuff) {
				cout << "The result is, we have " << A23 << " choices for the A:s\n";
			}
			if(A23 == 0) continue;


			ll f1 = amB - f2;
			ll d1 = f1 - a1;
			ll A1 = dp[d1][amB - amountOfB];
			if(printStuff) {
				cout << "In this case we have " << A1 << " choices for A1\n";
				cout << "That's because we added " << d1 << " new A:s to the grid\n";
				cout << "and there are " << amB - amountOfB << " B:s in the small area\n";
				cout << "The amount of B:s hitted is " << amountOfB << "\n";
			}
			ll f4 = n - 2*f2 - f1 - aA;
			if(f4 > 0 && n - amB - aA <= 0) continue;
			ll A4 = 1;
			for(ll i = 1; i <= f4; ++i) {
				A4 *= i;
				A4 %= M;
			}


			ll B = dp[n - amB][aA + f4];

			ll cur = A23;
			cur %= M;
			cur *= A1;
			cur %= M;
			cur *= A4;
			cur %= M;
			cur *= B;
			cur %= M;
			if(printStuff) {
				cout << "Statistics for " << f2 << " " << amountOfB << "\n";
				cout << "Number of ways for A:s " << A1*A23*A4 << "\n";
				cout << "Number of ways for A1 is " << A1 << " and for A23 it's " << A23 << " and for A4 " << A4 << "\n";
				cout << "The size of A4 is " << n - amB - aA << " and amount to be added there is " << f4 << "\n";
				cout << "Amounts to be added are " << d1 << " " << f2 - a2 << " " << f2 - a3 << " " << f4 << "\n";
				cout << "Number of ways for B:s " << B << "\n";
				cout << "Total number of ways: " << A1*A23*A4*B << "\n";
				cout << "\n\n";
			}
			ans += cur;
			ans %= M;
		}
	}

	cout << ans << "\n";


}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
2
..
..
view   save

correct output
2
view   save

user output
2
view   save

Test 2

Group: 1

Verdict: ACCEPTED

input
2
..
A.
view   save

correct output
1
view   save

user output
1
view   save

Test 3

Group: 1

Verdict: ACCEPTED

input
2
B.
.A
view   save

correct output
0
view   save

user output
0
view   save

Test 4

Group: 1

Verdict: ACCEPTED

input
3
...
...
...
view   save

correct output
12
view   save

user output
12
view   save

Test 5

Group: 1

Verdict: ACCEPTED

input
4
....
....
....
....
view   save

correct output
216
view   save

user output
216
view   save

Test 6

Group: 1

Verdict: ACCEPTED

input
5
.....
.....
.....
.....
.....
view   save

correct output
5280
view   save

user output
5280
view   save

Test 7

Group: 1

Verdict: ACCEPTED

input
5
....A
.....
.....
.....
A....
view   save

correct output
264
view   save

user output
264
view   save

Test 8

Group: 1

Verdict: ACCEPTED

input
5
B....
.....
.....
.A.B.
.B...
view   save

correct output
22
view   save

user output
22
view   save

Test 9

Group: 1

Verdict: ACCEPTED

input
5
B.A..
....A
.....
A.B..
....B
view   save

correct output
2
view   save

user output
2
view   save

Test 10

Group: 1

Verdict: ACCEPTED

input
5
A.B..
BA...
.B.A.
...BA
....B
view   save

correct output
1
view   save

user output
1
view   save

Test 11

Group: 2

Verdict: ACCEPTED

input
10
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
view   save

correct output
306442892
view   save

user output
306442892
view   save

Test 12

Group: 2

Verdict: ACCEPTED

input
50
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
...
view   save

correct output
694861480
view   save

user output
694861480
view   save

Test 13

Group: 2

Verdict: ACCEPTED

input
111
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
view   save

correct output
555319110
view   save

user output
555319110
view   save

Test 14

Group: 2

Verdict: ACCEPTED

input
222
.................................
.................................
.................................
.................................
.................................
view   save

correct output
108372237
view   save

user output
108372237
view   save

Test 15

Group: 2

Verdict: ACCEPTED

input
333
.................................
.................................
.................................
view   save

correct output
259107857
view   save

user output
259107857
view   save

Test 16

Group: 2

Verdict: ACCEPTED

input
444
.................................
.................................
.................................
view   save

correct output
19906314
view   save

user output
19906314
view   save

Test 17

Group: 2

Verdict: ACCEPTED

input
497
.................................
.................................
view   save

correct output
224313667
view   save

user output
224313667
view   save

Test 18

Group: 2

Verdict: ACCEPTED

input
498
.................................
.................................
view   save

correct output
929574601
view   save

user output
929574601
view   save

Test 19

Group: 2

Verdict: ACCEPTED

input
499
.................................
.................................
view   save

correct output
600226043
view   save

user output
600226043
view   save

Test 20

Group: 2

Verdict: ACCEPTED

input
500
.................................
.................................
view   save

correct output
198353194
view   save

user output
198353194
view   save

Test 21

Group: 3

Verdict: ACCEPTED

input
499
.................................
.........................A.......
view   save

correct output
840243733
view   save

user output
840243733
view   save

Test 22

Group: 3

Verdict: ACCEPTED

input
499
........................A........
..........A...B..................
view   save

correct output
4146290
view   save

user output
4146290
view   save

Test 23

Group: 3

Verdict: ACCEPTED

input
499
B.........A......................
....AB...........................
view   save

correct output
173518884
view   save

user output
173518884
view   save

Test 24

Group: 3

Verdict: ACCEPTED

input
499
...A....B........................
.........A...B...................
view   save

correct output
20044800
view   save

user output
20044800
view   save

Test 25

Group: 3

Verdict: ACCEPTED

input
499
AB...............................
....B.......A....................
view   save

correct output
2
view   save

user output
2
view   save

Test 26

Group: 3

Verdict: ACCEPTED

input
500
.................................
.................................
view   save

correct output
121064146
view   save

user output
121064146
view   save

Test 27

Group: 3

Verdict: ACCEPTED

input
500
.................................
..................A..............
view   save

correct output
848435259
view   save

user output
848435259
view   save

Test 28

Group: 3

Verdict: ACCEPTED

input
500
.....B........A..................
..........B...............A......
view   save

correct output
296240911
view   save

user output
296240911
view   save

Test 29

Group: 3

Verdict: ACCEPTED

input
500
.A......B........................
..A.............B................
view   save

correct output
2196
view   save

user output
2196
view   save

Test 30

Group: 3

Verdict: ACCEPTED

input
500
...AB............................
.A.....B.........................
view   save

correct output
1
view   save

user output
1
view   save