Submission #845682

#	Time	Username	Problem	Language	Result	Execution time	Memory
845682		vjudge1	Skandi (COCI20_skandi)	C++17	18 / 110	10018 ms	604 KiB

Main

#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 / 18
• Subtask 2: 0 / 32
• Subtask 3: 0 / 60