oj.uz

Submission #845682

# Submission time Handle Problem Language Result Execution time Memory
845682 2023-09-06T14:54:48 Z vjudge1 Skandi (COCI20_skandi) C++17
18 / 110
 10000 ms 604 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;
}

vector <tuple <int, int, bool>> cev;
vector <tuple <int, int, bool>> anss;

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())
    {
        if(adim < ans)
        {
            anss = cev;
        }

        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)
                {
                    cev.emplace_back(i, j, 1);
                    for(auto &[a, b] : vec) arr[a][b] = '2';
                    f(adim +1);
                    for(auto &[a, b] : vec) arr[a][b] = '0';
                    cev.pop_back();
                }

                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)
                {
                    cev.emplace_back(i, j, 0);
                    for(auto &[a, b] : vec) arr[a][b] = '2';
                    f(adim +1);
                    for(auto &[a, b] : vec) arr[a][b] = '0';
                    cev.pop_back();
                }
            }
        }
    }
}

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 << "\n";
    for(auto &[a, b, c] : anss)
    {
        cout << a << " " << b << " " << (c ? "DESNO" : "DOLJE") << "\n";
    }

    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
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 344 KB Correct.
4 Correct 0 ms 348 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 1 ms 348 KB Correct.
9 Correct 1 ms 348 KB Correct.
10 Correct 1 ms 344 KB Correct.
11 Correct 1 ms 348 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 1 ms 348 KB Correct.
14 Correct 1 ms 512 KB Correct.
15 Correct 1 ms 344 KB Correct.
16 Correct 0 ms 348 KB Correct.
17 Correct 0 ms 348 KB Correct.
18 Correct 0 ms 348 KB Correct.
19 Correct 0 ms 348 KB Correct.
20 Correct 0 ms 400 KB Correct.
21 Correct 1 ms 348 KB Correct.
22 Correct 0 ms 348 KB Correct.
23 Correct 0 ms 348 KB Correct.

Subtask #2
0.0 / 32.0

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

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 344 KB Correct.
4 Correct 0 ms 348 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 1 ms 348 KB Correct.
9 Correct 1 ms 348 KB Correct.
10 Correct 1 ms 344 KB Correct.
11 Correct 1 ms 348 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 1 ms 348 KB Correct.
14 Correct 1 ms 512 KB Correct.
15 Correct 1 ms 344 KB Correct.
16 Correct 0 ms 348 KB Correct.
17 Correct 0 ms 348 KB Correct.
18 Correct 0 ms 348 KB Correct.
19 Correct 0 ms 348 KB Correct.
20 Correct 0 ms 400 KB Correct.
21 Correct 1 ms 348 KB Correct.
22 Correct 0 ms 348 KB Correct.
23 Correct 0 ms 348 KB Correct.
24 Execution timed out 10018 ms 604 KB Time limit exceeded
25 Halted 0 ms 0 KB -