Task: | Torni |
Sender: | AtskaFin |
Submission time: | 2020-09-26 15:43:56 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 15 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 15 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.08 s | 1, 2, 3 | details |
#2 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3 | details |
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: TIME LIMIT EXCEEDED
input |
---|
100 1 2 3 4 ... |
correct output |
---|
2 8 34 148 650 ... |
user output |
---|
(empty) |
Test 3
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
100 996306 650655 896240 821967 ... |
correct output |
---|
87350005 606189151 122595036 193572715 227926807 ... |
user output |
---|
(empty) |