oj.uz

Submission #845671

# Submission time Handle Problem Language Result Execution time Memory
845671 2023-09-06T14:51:24 Z vjudge1 Skandi (COCI20_skandi) C++17
9 / 110
 10000 ms 600 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int INF = 1e9 + 7;

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    #define OPEN freopen(".in", "r", stdin); \
                 freopen(".out", "w", stdout);
#else
    #define OPEN void(23);
#endif


char arr[505][505];
int n, m;
bool check()
{
    bool ok = true;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) 
            ok &= (arr[i][j] != '0');

    return ok;
}

int ans = INF;
inline void f(int adim)
{
    /*
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cerr << arr[i][j] << " \n"[j == m];
    cerr << "\n";
    */
    if(check())
    {
        ans = min(ans, adim);
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(arr[i][j] == '1')
            {
                bool change = false;
                vector <pair <int, int>> vec;
                for(int k = j +1; k <= m; k++)
                {
                    if(arr[i][k] == '1') break;
                    change |= arr[i][k] == '0';
                    if(arr[i][k] == '0') vec.emplace_back(i, k);
                }
                if(change)
                {
                    for(auto &[a, b] : vec) arr[a][b] = '2';
                    f(adim +1);
                    for(auto &[a, b] : vec) arr[a][b] = '0';
                }

                change = false;
                vec.clear();
                for(int k = i +1; k <= n; k++)
                {
                    if(arr[k][j] == '1') break;
                    change |= arr[k][j] == '0';
                    if(arr[k][j] == '0') vec.emplace_back(k, j);
                }
                if(change)
                {
                    for(auto &[a, b] : vec) arr[a][b] = '2';
                    f(adim +1);
                    for(auto &[a, b] : vec) arr[a][b] = '0';
                }
            }
        }
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> arr[i][j];

    f(0);
    cout << ans;

    return;
}

int32_t main()
{
    OPEN;

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1; //cin >> t;
    while(t--)
    {
        solve();
    }
}

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 1 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 0 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 1 ms 464 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 0 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 1 ms 464 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 0 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 1 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 0 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 0 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 1 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 0 ms 348 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #2
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10014 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 1 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 0 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 1 ms 464 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 0 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 1 ms 464 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 0 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 1 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 1 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 0 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 0 ms 344 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 1 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 0 ms 348 KB First line is correct, but the reconstruction is not properly formatted.
24 Execution timed out 10014 ms 600 KB Time limit exceeded
25 Halted 0 ms 0 KB -