oj.uz

Submission #212315

# Submission time Handle Problem Language Result Execution time Memory
212315 2020-03-22T17:06:26 Z model_code Skandi (COCI20_skandi) C++17
25 / 110
 2771 ms 262036 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxm = 10;
const int maxn = 505;
const int inf = 1e9;
int max_mask;
int N, M;
int dp[maxn][(1 << maxm)];
int prijelaz[maxn][(1 << maxm)];
int space[maxn][maxm];
int sol = inf;
int mask_sol;
vector <int> v[maxn][(1 << maxm)];
string s[maxn];

int get_val(int x, int line)
{
    int val = 0;
        for (int k = 1; k <= M; k++)
            if (s[line][k] == '0')
                val += ((1 << (k - 1)) & x);
    return val;
}

int get_plus(int x, int line)
{
    int plus = 0;
    for (int k = 1; k < M; k++)
         if (s[line][k] == '1')
             if (((1 << (k - 1)) & x) == (1 << (k - 1)))
                plus++;
    return plus;
}

void input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> s[i];
}

void solve()
{
    max_mask = (1 << (M - 1));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < max_mask; j++)
            dp[i][j] = prijelaz[i][j] = inf;
    for (int i = 0; i < max_mask; i++)
        dp[0][i] = __builtin_popcount(i);
    for (int i = 1; i < N; i++)
    {
        int cnt = -1;
        for (int j = M - 1; j >= 0; j--)
        {
            cnt++;
            if (s[i][j] == '1') {space[i][j] = cnt; cnt = -1;}
        }
    }
    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (s[i][j] == '1')
            {
                int control = 0;
                for (int k = j + 1; k <= j + space[i][j]; k++)
                    control |= (1 << (k - 1));
                for (int k = 0; k < max_mask; k++)
                    if ((k & control) != control)
                        {dp[i - 1][k]++; v[i - 1][k].push_back(j + 1);}
            }
        }
        for (int j = 0; j < max_mask; j++)
        {
            int val = get_val(j, i);
            prijelaz[i][val] = min(prijelaz[i][val], dp[i - 1][j]);
        }

        for (int j = 0; j < max_mask; j++)
        {
            int val = get_val(j, i);
            dp[i][j] = prijelaz[i][val] + get_plus(j, i);
        }
    }

    for (int i = 0; i < max_mask; i++)
    {
        if (dp[N - 1][i] < sol)
        {
            sol = dp[N - 1][i];
            mask_sol = i;
        }
    }

    cout << sol << '\n';
}

void reconstruct()
{
    int last_mask_sol = mask_sol;
    int line = N - 1;
    int minx = 1e9;
    int const_val;

    while (line >= 0)
    {
        for (int i = 1; i < M; i++)
        {
            if (s[line][i] == '1')
                if ((mask_sol & (1 << (i - 1))) == (1 << (i - 1)))
                    cout << line + 1 << ' ' << i + 1 << " DOLE\n";
        }
        for (int i = 0; i < v[line][mask_sol].size(); i++)
            cout << line + 2 << ' ' << v[line][mask_sol][i] << " DESNO\n";

        if (line > 0)
        {
            const_val = get_val(mask_sol, line);
            last_mask_sol = mask_sol;
            minx = 1e9;

            for (int i = 0; i < max_mask; i++)
            {
                if (get_val(i, line) == const_val)
                    if (dp[line - 1][i] < minx)
                        {minx = dp[line - 1][i]; mask_sol = i;}
            }
        }

        line--;
    }

    return;
}

int main()
{
    input();
    solve();
    reconstruct();
}

Compilation message

skandi.cpp: In function 'void reconstruct()':
skandi.cpp:114:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < v[line][mask_sol].size(); i++)
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
skandi.cpp:101:9: warning: variable 'last_mask_sol' set but not used [-Wunused-but-set-variable]
     int last_mask_sol = mask_sol;
         ^~~~~~~~~~~~~

Subtask #1
9.0 / 18.0

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

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 16000 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 13 ms 14080 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 14 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 14 ms 13952 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 13 ms 13952 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 16 ms 13488 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 14 ms 13312 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 19 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 47 ms 24476 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 62 ms 23544 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 51 ms 23928 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 55 ms 24284 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 69 ms 23788 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 55 ms 23928 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 53 ms 24312 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 56 ms 24568 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 54 ms 24440 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 58 ms 24416 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 55 ms 24056 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 53 ms 24440 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 66 ms 24296 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 53 ms 24192 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 63 ms 24184 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 46 ms 24444 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 59 ms 24344 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 68 ms 23800 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12544 KB Correct.
2 Partially correct 12 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
3 Correct 11 ms 12544 KB Correct.
4 Partially correct 13 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
5 Correct 13 ms 12520 KB Correct.
6 Correct 12 ms 12544 KB Correct.
7 Partially correct 12 ms 12520 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 14 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
9 Correct 13 ms 12544 KB Correct.
10 Partially correct 12 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
11 Correct 11 ms 12544 KB Correct.
12 Partially correct 14 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
13 Correct 11 ms 12544 KB Correct.
14 Correct 13 ms 12544 KB Correct.
15 Correct 14 ms 12544 KB Correct.
16 Partially correct 13 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
17 Correct 12 ms 12544 KB Correct.
18 Partially correct 15 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
19 Correct 13 ms 12520 KB Correct.
20 Correct 15 ms 12520 KB Correct.
21 Correct 14 ms 12520 KB Correct.
22 Partially correct 12 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
23 Correct 14 ms 12544 KB Correct.
24 Partially correct 13 ms 16000 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 13 ms 14080 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 14 ms 15360 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 14 ms 13952 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 13 ms 13952 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 16 ms 13488 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 14 ms 13312 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 19 ms 15232 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 47 ms 24476 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 62 ms 23544 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 51 ms 23928 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 55 ms 24284 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 69 ms 23788 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 55 ms 23928 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 53 ms 24312 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 56 ms 24568 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 54 ms 24440 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 58 ms 24416 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 55 ms 24056 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 53 ms 24440 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 66 ms 24296 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 53 ms 24192 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 63 ms 24184 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 46 ms 24444 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 59 ms 24344 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 68 ms 23800 KB First line is correct, but the reconstruction is not properly formatted.
50 Incorrect 2771 ms 262036 KB First line is not correct.
51 Halted 0 ms 0 KB -