CSES - Datatähti 2025 alku - Results
Submission details
Task:Kortit II
Sender:OorigamiK
Submission time:2024-11-09 09:59:41 +0200
Language:C++ (C++20)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1--1, 2, 3, 4, 5details
#2--2, 3, 4, 5details
#3--3, 4, 5details
#4--4, 5details
#5--5details
#6--5details

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:

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:

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:

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:

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:

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:

input
1000
2000 1107 508
2000 1372 249
2000 588 65
2000 1739 78
...

correct output
750840601
678722180
744501884
159164549
868115056
...

user output
(empty)