oj.uz

Submission #967316

# Submission time Handle Problem Language Result Execution time Memory
967316 2024-04-21T20:29:43 Z amine_aroua Paint By Numbers (IOI16_paint) C++17
32 / 100
 1 ms 444 KB 
#pragma once
#include <bits/stdc++.h>
using namespace std;
#define forr(i, x , y) for(int i = x ; i<=y;i++)
#define fore(i , x) for(int i = 0 ; i<x;i++)
auto compute_dp(int n , int K , string s , vector<int> c)
{
    vector<vector<int>> dp(n + 1 , vector<int>(K + 1 , 0));
    vector<vector<int>> pref(2 , vector<int>(n + 1 ,0));
    forr(i , 1, n)
    {
        if(s[i - 1] == 'X')
            pref[1][i]++;
        if(s[i - 1] == '_')
            pref[0][i]++;
        fore(j , 2)
        {
            pref[j][i] += pref[j][i - 1];
        }
    }
    forr(i , 0 , n)
    {

            if(pref[1][i] == 0)
                dp[i][0] = 1;
    }
    forr(i , 1 , n)
    {
        forr(j , 1 , K) {
            int w = dp[i - 1][j];
            int b = 0;
            int l = i - c[j - 1] + 1;
            int r = i;
            if(l >= 1)
            {
                if(pref[0][r] - pref[0][l - 1] == 0)
                {
                    if(i != c[j - 1])
                    {
                        if(s[i - c[j - 1]] != 'X')
                        {
                            b = dp[i - c[j - 1] - 1][j - 1];
                        }
                    }
                    else
                        b = dp[i - c[j - 1]][j - 1];
                }
            }
            if(s[i - 1] == '_')
                dp[i][j] = w;
            else if(s[i - 1] == 'X')
            {
                dp[i][j] = b;
            }
            else
            {
                dp[i][j] = w;
                dp[i][j]|=b;
            }
        }
    }
    return dp;
}
std::string solve_puzzle(std::string s, std::vector<int> c)
{
    int n = (int)s.size();
    int K = (int)c.size();
    for(auto &C: s)
        if(C == '.')C='?';
    auto dpL = compute_dp(n , K, s , c);
    reverse(s.begin() , s.end());
    reverse(c.begin() , c.end());
    auto dpR = compute_dp(n , K , s ,c);
    reverse(dpR.begin() + 1 , dpR.end());
    dpR.push_back(dpR[0]);
    reverse(s.begin() , s.end());
    reverse(c.begin() , c.end());
    vector<int> can_black(n +2 , 0);
    vector<vector<int>> pref(2 ,vector<int>(n + 1 , 0));
    forr(i , 1 , n)
    {
        pref[0][i] = pref[0][i - 1] + (s[i - 1] == '_');
        pref[1][i] = pref[1][i - 1] + (s[i - 1] == 'X');
    }

    vector<int> val(n , 0);
    forr(i , 1 , n)
    {
        if(s[i - 1] == '?')
        {
            int cur = 0;
            forr(k , 0 , K)
            {
                cur|=(dpL[i - 1][k] && dpR[i + 1][K - k]);
            }
            if(cur == 1)
                val[i-1]|=1;
        }
    }
    forr(i , 1 , n)
    {
        if(s[i - 1] == '?' || s[i - 1] == 'X')
        {
            forr(k , 0 , K - 1)
            {
                int lt = i , rt = c[k] + i - 1;
                if(rt > n)
                    continue;
                bool checkL = ((i == 1) || s[i - 2] != 'X');
                bool checkR = ((rt == n) || s[rt] != 'X');
                int dpLeft ;
                if(i <= 2)
                    dpLeft = (i <= 2 && k == 0);
                else
                    dpLeft = dpL[i - 2][k];
                int dpRight;
                if(rt + 2 > n)
                    dpRight= (rt + 2 > n && k + 1 == K);
                else
                    dpRight = dpR[rt + 2][K - k - 1];
                if(checkL && checkR && dpLeft && dpRight && ((pref[0][rt] - pref[0][i - 1]) == 0))
                {
                    can_black[lt]++;
                    can_black[min(n  + 1, rt + 1)]--;
                }
            }
        }
    }
    forr(i , 1 , n)
    {
        can_black[i]+=can_black[i - 1];
        if(can_black[i])
            val[i - 1]|=2;
    }
    fore(i , n)
    {
        if(val[i] == 1)
            s[i] = '_';
        else if(val[i] == 2)
            s[i] = 'X';
        else
            s[i] = '?';
    }
    return s;
}

Compilation message

paint.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 13, m = 1
2 Correct 0 ms 348 KB n = 18, m = 1
3 Correct 0 ms 348 KB n = 17, m = 1
4 Correct 0 ms 348 KB n = 1, m = 1
5 Correct 1 ms 348 KB n = 20, m = 1
6 Correct 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 348 KB n = 20, m = 1

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 13, m = 1
2 Correct 0 ms 348 KB n = 18, m = 1
3 Correct 0 ms 348 KB n = 17, m = 1
4 Correct 0 ms 348 KB n = 1, m = 1
5 Correct 1 ms 348 KB n = 20, m = 1
6 Correct 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 348 KB n = 20, m = 1
8 Correct 0 ms 348 KB n = 20, m = 5
9 Correct 0 ms 348 KB n = 18, m = 3
10 Correct 0 ms 348 KB n = 17, m = 2
11 Correct 0 ms 348 KB n = 20, m = 2
12 Correct 0 ms 348 KB n = 17, m = 4
13 Correct 0 ms 348 KB n = 17, m = 6
14 Correct 0 ms 348 KB n = 17, m = 1
15 Correct 1 ms 348 KB n = 17, m = 4
16 Correct 0 ms 348 KB n = 13, m = 3
17 Correct 0 ms 348 KB n = 18, m = 4
18 Correct 0 ms 348 KB n = 20, m = 10
19 Correct 0 ms 348 KB n = 19, m = 10

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 13, m = 1
2 Correct 0 ms 348 KB n = 18, m = 1
3 Correct 0 ms 348 KB n = 17, m = 1
4 Correct 0 ms 348 KB n = 1, m = 1
5 Correct 1 ms 348 KB n = 20, m = 1
6 Correct 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 348 KB n = 20, m = 1
8 Correct 0 ms 348 KB n = 20, m = 5
9 Correct 0 ms 348 KB n = 18, m = 3
10 Correct 0 ms 348 KB n = 17, m = 2
11 Correct 0 ms 348 KB n = 20, m = 2
12 Correct 0 ms 348 KB n = 17, m = 4
13 Correct 0 ms 348 KB n = 17, m = 6
14 Correct 0 ms 348 KB n = 17, m = 1
15 Correct 1 ms 348 KB n = 17, m = 4
16 Correct 0 ms 348 KB n = 13, m = 3
17 Correct 0 ms 348 KB n = 18, m = 4
18 Correct 0 ms 348 KB n = 20, m = 10
19 Correct 0 ms 348 KB n = 19, m = 10
20 Correct 1 ms 348 KB n = 100, m = 5
21 Correct 0 ms 348 KB n = 90, m = 3
22 Correct 0 ms 344 KB n = 86, m = 2
23 Correct 0 ms 344 KB n = 81, m = 4
24 Correct 0 ms 444 KB n = 89, m = 10
25 Correct 1 ms 344 KB n = 81, m = 23
26 Correct 0 ms 344 KB n = 86, m = 8
27 Correct 0 ms 348 KB n = 53, m = 22
28 Correct 1 ms 348 KB n = 89, m = 35
29 Correct 1 ms 348 KB n = 63, m = 25
30 Correct 1 ms 348 KB n = 100, m = 50
31 Correct 1 ms 344 KB n = 99, m = 50

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 13, m = 1
2 Correct 0 ms 348 KB n = 18, m = 1
3 Correct 0 ms 348 KB n = 17, m = 1
4 Correct 0 ms 348 KB n = 1, m = 1
5 Correct 1 ms 348 KB n = 20, m = 1
6 Correct 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 348 KB n = 20, m = 1
8 Correct 0 ms 348 KB n = 20, m = 5
9 Correct 0 ms 348 KB n = 18, m = 3
10 Correct 0 ms 348 KB n = 17, m = 2
11 Correct 0 ms 348 KB n = 20, m = 2
12 Correct 0 ms 348 KB n = 17, m = 4
13 Correct 0 ms 348 KB n = 17, m = 6
14 Correct 0 ms 348 KB n = 17, m = 1
15 Correct 1 ms 348 KB n = 17, m = 4
16 Correct 0 ms 348 KB n = 13, m = 3
17 Correct 0 ms 348 KB n = 18, m = 4
18 Correct 0 ms 348 KB n = 20, m = 10
19 Correct 0 ms 348 KB n = 19, m = 10
20 Correct 1 ms 348 KB n = 100, m = 5
21 Correct 0 ms 348 KB n = 90, m = 3
22 Correct 0 ms 344 KB n = 86, m = 2
23 Correct 0 ms 344 KB n = 81, m = 4
24 Correct 0 ms 444 KB n = 89, m = 10
25 Correct 1 ms 344 KB n = 81, m = 23
26 Correct 0 ms 344 KB n = 86, m = 8
27 Correct 0 ms 348 KB n = 53, m = 22
28 Correct 1 ms 348 KB n = 89, m = 35
29 Correct 1 ms 348 KB n = 63, m = 25
30 Correct 1 ms 348 KB n = 100, m = 50
31 Correct 1 ms 344 KB n = 99, m = 50
32 Incorrect 0 ms 348 KB char #4 differ - expected: '_', found: '?'
33 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 13, m = 1
2 Correct 0 ms 348 KB n = 18, m = 1
3 Correct 0 ms 348 KB n = 17, m = 1
4 Correct 0 ms 348 KB n = 1, m = 1
5 Correct 1 ms 348 KB n = 20, m = 1
6 Correct 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 348 KB n = 20, m = 1
8 Correct 0 ms 348 KB n = 20, m = 5
9 Correct 0 ms 348 KB n = 18, m = 3
10 Correct 0 ms 348 KB n = 17, m = 2
11 Correct 0 ms 348 KB n = 20, m = 2
12 Correct 0 ms 348 KB n = 17, m = 4
13 Correct 0 ms 348 KB n = 17, m = 6
14 Correct 0 ms 348 KB n = 17, m = 1
15 Correct 1 ms 348 KB n = 17, m = 4
16 Correct 0 ms 348 KB n = 13, m = 3
17 Correct 0 ms 348 KB n = 18, m = 4
18 Correct 0 ms 348 KB n = 20, m = 10
19 Correct 0 ms 348 KB n = 19, m = 10
20 Correct 1 ms 348 KB n = 100, m = 5
21 Correct 0 ms 348 KB n = 90, m = 3
22 Correct 0 ms 344 KB n = 86, m = 2
23 Correct 0 ms 344 KB n = 81, m = 4
24 Correct 0 ms 444 KB n = 89, m = 10
25 Correct 1 ms 344 KB n = 81, m = 23
26 Correct 0 ms 344 KB n = 86, m = 8
27 Correct 0 ms 348 KB n = 53, m = 22
28 Correct 1 ms 348 KB n = 89, m = 35
29 Correct 1 ms 348 KB n = 63, m = 25
30 Correct 1 ms 348 KB n = 100, m = 50
31 Correct 1 ms 344 KB n = 99, m = 50
32 Incorrect 0 ms 348 KB char #4 differ - expected: '_', found: '?'
33 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 13, m = 1
2 Correct 0 ms 348 KB n = 18, m = 1
3 Correct 0 ms 348 KB n = 17, m = 1
4 Correct 0 ms 348 KB n = 1, m = 1
5 Correct 1 ms 348 KB n = 20, m = 1
6 Correct 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 348 KB n = 20, m = 1
8 Correct 0 ms 348 KB n = 20, m = 5
9 Correct 0 ms 348 KB n = 18, m = 3
10 Correct 0 ms 348 KB n = 17, m = 2
11 Correct 0 ms 348 KB n = 20, m = 2
12 Correct 0 ms 348 KB n = 17, m = 4
13 Correct 0 ms 348 KB n = 17, m = 6
14 Correct 0 ms 348 KB n = 17, m = 1
15 Correct 1 ms 348 KB n = 17, m = 4
16 Correct 0 ms 348 KB n = 13, m = 3
17 Correct 0 ms 348 KB n = 18, m = 4
18 Correct 0 ms 348 KB n = 20, m = 10
19 Correct 0 ms 348 KB n = 19, m = 10
20 Correct 1 ms 348 KB n = 100, m = 5
21 Correct 0 ms 348 KB n = 90, m = 3
22 Correct 0 ms 344 KB n = 86, m = 2
23 Correct 0 ms 344 KB n = 81, m = 4
24 Correct 0 ms 444 KB n = 89, m = 10
25 Correct 1 ms 344 KB n = 81, m = 23
26 Correct 0 ms 344 KB n = 86, m = 8
27 Correct 0 ms 348 KB n = 53, m = 22
28 Correct 1 ms 348 KB n = 89, m = 35
29 Correct 1 ms 348 KB n = 63, m = 25
30 Correct 1 ms 348 KB n = 100, m = 50
31 Correct 1 ms 344 KB n = 99, m = 50
32 Incorrect 0 ms 348 KB char #4 differ - expected: '_', found: '?'
33 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 13, m = 1
2 Correct 0 ms 348 KB n = 18, m = 1
3 Correct 0 ms 348 KB n = 17, m = 1
4 Correct 0 ms 348 KB n = 1, m = 1
5 Correct 1 ms 348 KB n = 20, m = 1
6 Correct 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 348 KB n = 20, m = 1
8 Correct 0 ms 348 KB n = 20, m = 5
9 Correct 0 ms 348 KB n = 18, m = 3
10 Correct 0 ms 348 KB n = 17, m = 2
11 Correct 0 ms 348 KB n = 20, m = 2
12 Correct 0 ms 348 KB n = 17, m = 4
13 Correct 0 ms 348 KB n = 17, m = 6
14 Correct 0 ms 348 KB n = 17, m = 1
15 Correct 1 ms 348 KB n = 17, m = 4
16 Correct 0 ms 348 KB n = 13, m = 3
17 Correct 0 ms 348 KB n = 18, m = 4
18 Correct 0 ms 348 KB n = 20, m = 10
19 Correct 0 ms 348 KB n = 19, m = 10
20 Correct 1 ms 348 KB n = 100, m = 5
21 Correct 0 ms 348 KB n = 90, m = 3
22 Correct 0 ms 344 KB n = 86, m = 2
23 Correct 0 ms 344 KB n = 81, m = 4
24 Correct 0 ms 444 KB n = 89, m = 10
25 Correct 1 ms 344 KB n = 81, m = 23
26 Correct 0 ms 344 KB n = 86, m = 8
27 Correct 0 ms 348 KB n = 53, m = 22
28 Correct 1 ms 348 KB n = 89, m = 35
29 Correct 1 ms 348 KB n = 63, m = 25
30 Correct 1 ms 348 KB n = 100, m = 50
31 Correct 1 ms 344 KB n = 99, m = 50
32 Incorrect 0 ms 348 KB char #4 differ - expected: '_', found: '?'
33 Halted 0 ms 0 KB -