Submission #1003367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1003367	2024-06-20T09:18:17 Z	Nailuj_217	Dijamant (COCI22_dijamant)	C++17	20 / 70	1000 ms	3400 KB

Main

#include <bits/stdc++.h>
#define l long long
using namespace std;


const l INF = 1LL<<15;

array<vector<l>, 2005> rows;
array<l, 2005> positions;



int main() {

    l n, m;
    cin >> n >> m;
    string row;
    if (n == 1 || m == 1) {
        cout << 0 << endl;
        return 0;
    }

    l sum = 0;

    for (int i = 1; i <= n; i++) {
        cin >> row;
        for (int j = 0; j < row.size(); j++) {
            if (row[j] == '#') rows[i].push_back(j+1);
        }
    }
    l dist_to_left;

    for (int i = 2; i < n; i++) {
        positions.fill(0);
        for (int j = 1; j < m; j++) {
            for (int k = 1; k <= n; k++) {
                if (positions[k] == INF) continue;
                if (rows[k].empty()) {
                    positions[k] = INF;
                    continue;
                }
                if (rows[k][positions[k]] < j) {
                    if (rows[k].size() > positions[k]+1) positions[k]++; 
                    else positions[k] = INF;
                }
            }
            if (!positions[i]) continue;
            if (positions[i] == INF) continue;
            dist_to_left = j - rows[i][positions[i]-1];
            assert(dist_to_left >= 0);
            if (i - dist_to_left < 1 || i + dist_to_left > n || j + dist_to_left > m) continue;
            if (j + dist_to_left != rows[i][positions[i]]) continue;

            bool is_valid = true;

            // for (int k = i-dist_to_left+1; k < i+dist_to_left; k++)
            //     if (!positions[k] || positions[k] == INF) 
            //         is_valid = false;
                    
            if (!is_valid) continue;
            l c = 0;
            for (int k = i - dist_to_left; k < i; k++) {
                assert(k > 0);
                if (positions[k] == INF) {
                    is_valid = false;
                    break;
                }
                if (c == 0) {
                    if (rows[k][positions[k]] != j) {
                        is_valid = false;
                        break;
                    }
                } else {
                    if (positions[k] == 0 || rows[k][positions[k]-1] != j-c) {
                        is_valid = false;
                        break;
                    } 
                    if (positions[k] == 0 || rows[k][positions[k]] != j+c) {
                        is_valid = false;
                        break;
                    } 
                }
                c++;
            }
            c = 0;
            for (int k = i + dist_to_left; k > i; k--) {
                assert(k <= n);
                if (positions[k] == INF) {
                    is_valid = false;
                    break;
                }
                if (c == 0) {
                    if (rows[k][positions[k]] != j) {
                        is_valid = false;
                        break;
                    }
                } else {
                    if (positions[k] == 0 || rows[k][positions[k]-1] != j-c) {
                        is_valid = false;
                        break;
                    } 
                    if (positions[k] == 0 || rows[k][positions[k]] != j+c) {
                        is_valid = false;
                        break;
                    } 
                }
                c++;
            }
            if (is_valid) {
                sum++;
             continue;}
        }
    }



    cout << sum << endl;





    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:27:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int j = 0; j < row.size(); j++) {
      |                         ~~^~~~~~~~~~~~
Main.cpp:43:40: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'std::array<long long int, 2005>::value_type' {aka 'long long int'} [-Wsign-compare]
   43 |                     if (rows[k].size() > positions[k]+1) positions[k]++;
      |                         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	3 ms	348 KB	Output is correct
4	Correct	2 ms	524 KB	Output is correct
5	Correct	2 ms	604 KB	Output is correct
6	Correct	2 ms	348 KB	Output is correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	2 ms	344 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct

Subtask #2

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	3 ms	348 KB	Output is correct
4	Correct	2 ms	524 KB	Output is correct
5	Correct	2 ms	604 KB	Output is correct
6	Correct	2 ms	348 KB	Output is correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	2 ms	344 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Execution timed out	1086 ms	3400 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-