CSES - Putka Open 2020 – 2/5 - Results
Submission details
Task:Torni
Sender:AtskaFin
Submission time:2020-09-26 15:43:56 +0300
Language:C++ (C++17)
Status:READY
Result:15
Feedback
groupverdictscore
#1ACCEPTED15
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.08 s1, 2, 3details
#2--2, 3details
#3--3details

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> torni;
int n;
int ratkaisut;
bool asetaPala(int x1, int y1, int x2, int y2) {
for (int i = y1; i <= y2; i++) {
for (int j = x1; j <= x2; j++) {
if (torni[i][j] == 1) return false;
}
}
for (int i = y1; i <= y2; i++) {
for (int j = x1; j <= x2; j++) {
torni[i][j] = 1;
}
}
return true;
}
void poistaPala(int x1, int y1, int x2, int y2) {
for (int i = y1; i <= y2; i++) {
for (int j = x1; j <= x2; j++) {
torni[i][j] = 0;
}
}
}
void haku(int x, int y) {
if (x == n && y == 1) { ratkaisut++; }
else if (x == n) { haku(0, y+1); }
else if (torni[y][x] == 1) { haku(x+1, y); }
else {
for (int i = y; i < 2; i++) {
for (int j = x; j < n; j++) {
bool onkoPalaAsetettu = asetaPala(x, y, j, i);
if (onkoPalaAsetettu) {
if (y == 1 && x + abs(x - j) + 1 == n) {
ratkaisut++;
} else {
haku(x + abs(x - j) + 1, y);
}
poistaPala(x, y, j, i);
}
}
}
}
}
int t;
int main() {
cin >> t;
for (int d = 0; d < t; d++) {
cin >> n;
torni.clear();
torni.resize(2);
for (int i = 0; i < 2; i++) {
torni[i].resize(n);
}
haku(0, 0);
cout << ratkaisut << "\n";
ratkaisut = 0;
}
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
1
2
3
4
...

correct output
2
8
34
148
650
...

user output
2
8
34
148
650
...

Test 2

Group: 2, 3

Verdict:

input
100
1
2
3
4
...

correct output
2
8
34
148
650
...

user output
(empty)

Test 3

Group: 3

Verdict:

input
100
996306
650655
896240
821967
...

correct output
87350005
606189151
122595036
193572715
227926807
...

user output
(empty)