Task: | Kortit II |
Sender: | OorigamiK |
Submission time: | 2024-11-09 09:59:41 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | TIME LIMIT EXCEEDED | 0 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
#4 | TIME LIMIT EXCEEDED | 0 |
#5 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | TIME LIMIT EXCEEDED | -- | 1, 2, 3, 4, 5 | details |
#2 | TIME LIMIT EXCEEDED | -- | 2, 3, 4, 5 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3, 4, 5 | details |
#4 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#5 | TIME LIMIT EXCEEDED | -- | 5 | details |
#6 | TIME LIMIT EXCEEDED | -- | 5 | details |
Compiler report
input/code.cpp: In function 'bool recArea(const int&, const int&, const int&, const int&, const std::vector<std::vector<std::vector<int> > >&)': input/code.cpp:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare] 8 | for (int color = 0; color < flowerSums.size(); color++) { | ~~~~~~^~~~~~~~~~~~~~~~~~~ input/code.cpp: In function 'int main()': input/code.cpp:81:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare] 81 | for (int color = 0; color < flowerSums.size(); color++) { | ~~~~~~^~~~~~~~~~~~~~~~~~~ input/code.cpp:103:17: warning: variable 'step1' set but not used [-Wunused-but-set-variable] 103 | int step1 = 1; | ^~~...
Code
#include <iostream>#include <string>#include <vector>#include <chrono>#include <algorithm>bool recArea(const int& x1, const int& x2, const int& y1, const int& y2, const std::vector<std::vector<std::vector<int>>>& flowerSums) {for (int color = 0; color < flowerSums.size(); color++) {int sum = 0;sum += flowerSums[color][x2][y2];sum += flowerSums[color][x1 - 1][y1 - 1];sum -= flowerSums[color][x1 - 1][y2];sum -= flowerSums[color][x2][y1 - 1];if (sum <= 0) {return false;}}return true;}int ask_for_input() {int n;//std::cin >> n;n = 200;return n;}int main(){auto start = std::chrono::high_resolution_clock::now();std::vector<std::string> flowers;int const n = ask_for_input();for (int i = 0; i < n; i++) {std::string s;//std::cin >> s;for (int r = 0; r < n; r++) {int k = (rand())%26;s += char(int('A') + k);}flowers.push_back(s);}std::vector<bool> theFlowers;for (int i = 0; i < 26; i++) {theFlowers.push_back(false);}for (std::string s : flowers) {for (int i = 0; i < n; i++) {int k = int(s[i]) - int('A');theFlowers[k] = true;}}std::vector<std::vector<std::vector<int>>> flowerSums;int y = 0;for (int j = 0; j < 26; j++) {if (theFlowers[j]) {flowerSums.push_back({});for (int i = 0; i <= n; i++) {flowerSums[y].push_back({});for (int k = 0; k <= n; k++) {flowerSums[y][i].push_back(0);}}y++;}}y = 0;for (int color = 0; color < 26; color++) {if (theFlowers[color]) {for (int k = 1; k <= n; k++) {for (int t = 1; t <= n; t++) {if (int(flowers[k - 1][t - 1]) - int('A') == color) {flowerSums[y][k][t]++;}}}y++;}}for (int color = 0; color < flowerSums.size(); color++) {for (int i = 2; i <= n; i++) {for (int j = 1; j <= n; j++) {flowerSums[color][i][j] += flowerSums[color][i - 1][j];}}for (int i = 1; i <= n; i++) {for (int j = 2; j <= n; j++) {flowerSums[color][i][j] += flowerSums[color][i][j - 1];}}}auto stop = std::chrono::high_resolution_clock::now();auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);std::cout << duration.count() << std::endl;long long numOfRec = 0;//std::cout << flowerSums[0][1][4] << std::endl;for (int x1 = 1; x1 <= n; x1++) {int ceils[201];std::fill(std::begin(ceils), std::end(ceils), n);for (int x2 = x1; x2 <= n; x2++) {int step1 = 1;int y1 = 1;while (y1 <= n) {int ceiling2 = ceils[y1];int flooring2 = y1;int step2 = (ceiling2 + flooring2) / 2;while (ceiling2 - flooring2 > 1) {if (recArea(x1, x2, y1, step2, flowerSums)) {ceiling2 = (ceiling2 + flooring2) / 2 + (ceiling2 + flooring2) % 2;}else {flooring2 = (ceiling2 + flooring2) / 2;}step2 = (ceiling2 + flooring2) / 2;}if (recArea(x1, x2, y1, flooring2, flowerSums)) {step2 = flooring2;}else if (recArea(x1, x2, y1, ceiling2, flowerSums)) {step2 = ceiling2;}else {step2 = n + 1;}step1 = y1;int ceiling1 = step2;int flooring1 = y1;int step1 = (ceiling1 + flooring1) / 2;while (ceiling1 - flooring1 > 1) {if (recArea(x1, x2, step1, step2, flowerSums)) {flooring1 = (ceiling1 + flooring1) / 2;}else {ceiling1 = (ceiling1 + flooring1) / 2 + (ceiling1 + flooring1) % 2;}step1 = (ceiling1 + flooring1) / 2;}if (recArea(x1, x2, flooring1, step2, flowerSums)) {step1 = flooring1;}else if (recArea(x1, x2, ceiling1, step2, flowerSums)) {step1 = ceiling1;}else {step1 = n + 1;}if (step1 <= n && step2 <= n) {std::fill(std::begin(ceils) + y1, std::begin(ceils) + step1, step2);//std::cout << 1 + step1 - y1 << " " << n + 1 - step2 << " " << x1 << " " << x2 << " " << (1 + step1 - y1) * (n - step2) << " " << y1 << " " << step1 << " " << step2 << std::endl;numOfRec += (1 + step1 - y1) * (n + 1 - step2);}y1 = step1 + 1;}}}stop = std::chrono::high_resolution_clock::now();duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);std::cout << duration.count() << std::endl;std::cout << numOfRec << std::endl;}
Test details
Test 1
Group: 1, 2, 3, 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
54 4 4 0 3 1 3 3 2 2 4 0 4 ... |
correct output |
---|
0 0 0 0 0 ... |
user output |
---|
(empty) |
Test 2
Group: 2, 3, 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
284 6 1 0 5 0 2 7 1 5 7 7 5 ... |
correct output |
---|
0 0 35280 0 36720 ... |
user output |
---|
(empty) |
Test 3
Group: 3, 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
841 19 3 12 19 19 13 19 7 13 20 11 15 ... |
correct output |
---|
40291066 0 0 0 0 ... |
user output |
---|
(empty) |
Test 4
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 15 12 6 7 1 6 44 4 26 6 6 5 ... |
correct output |
---|
0 5040 494558320 0 340694548 ... |
user output |
---|
(empty) |
Test 5
Group: 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 892 638 599 966 429 655 1353 576 1140 1403 381 910 ... |
correct output |
---|
0 0 0 249098285 0 ... |
user output |
---|
(empty) |
Test 6
Group: 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 2000 1107 508 2000 1372 249 2000 588 65 2000 1739 78 ... |
correct output |
---|
750840601 678722180 744501884 159164549 868115056 ... |
user output |
---|
(empty) |