oj.uz

Submission #967569

# Submission time Handle Problem Language Result Execution time Memory
967569 2024-04-22T12:55:02 Z amine_aroua Paint By Numbers (IOI16_paint) C++17
0 / 100
 0 ms 348 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++)
#define forn(i , x ,y) for(int i = x; i>=y;i--)
vector<vector<int>> pref;
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='?';
    pref.assign(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<vector<int>> dpL(n + 1 , vector<int>(K + 1 , 0)) , dpR(n + 3 , vector<int>(K + 1 , 0));
    dpL[0][0] = 1;
    forr(i , 1 , n)
    {
        forr(j , 0 , K) {
            if(j - 1 >= 0 && c[j - 1] <= i && pref[0][i] - pref[0][i - c[j - 1]] && (i - c[j - 1] <= 0 || s[i - c[j - 1] -1] != 'X'))
            {
                if(i - c[j - 1] == 0)
                {
                    if(j == 1)
                        pref[i][j]|=1;
                }
                else
                {
                    pref[i][j]|=pref[i - c[j - 1] - 1][j - 1];
                }
            }
            if(s[i -1] != 'X')
                dpL[i][j]|=dpL[i - 1][j];
        }
    }

    dpR[n + 1][K] = 1;
    dpR[n + 2][K] = 1;
    forn(i , n , 1)
    {
        forr(j , 0 , K) {
            if(j + 1 <= K && c[j] <= n - i + 1 && pref[0][i + c[j] - 1] - pref[0][i - 1] == 0 && (i + c[j] > n || s[i + c[j] - 1] != 'X'))
            {
                if(i + c[j] == n + 1)
                    if(j == K - 1)
                        dpR[i][j]|=1;
            }
            if(s[i -1] != 'X')
                dpR[i][j]|=dpR[i + 1][j];
        }
    }
    vector<int> can_black(n +5 , 0);

    vector<int> val(n , 0);
    forr(i , 1 , n)
    {
        if(s[i - 1] != 'X')
        {
            int cur = 0;
            forr(k , 0 , K)
            {
                cur|=(dpL[i - 1][k] && dpR[i + 1][k]);
            }
            if(cur == 1)
                val[i-1]|=1;
        }
    }
    forr(i , 1 , n)
    {
            forr(k , 0 , K - 1)
            {
                bool checkL = (i == 1 ? (k == 0) : (dpL[i - 2][k]&&s[i - 2] != 'X'));
                bool checkR = (i + c[k] - 1 <= n && dpR[i + c[k] + 1][k + 1]);
                bool check = (pref[0][i + c[k] - 1] - pref[0][i - 1] == 0 && (i + c[k] > n || s[i + c[k] - 1] != 'X'));
                if(checkL && checkR && check)
                {
                    if(i + c[k] > n)
                    {
                        if(k + 1 == K)
                        {
                            can_black[i]++;
                            can_black[i + c[k]]--;
                        }
                    }
                    else
                    {
                        can_black[i]++;
                        can_black[i + c[k]]--;
                    }
                }
            }
    }
    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB char #8 differ - expected: '?', found: 'X'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB char #8 differ - expected: '?', found: 'X'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB char #8 differ - expected: '?', found: 'X'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB char #8 differ - expected: '?', found: 'X'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB char #8 differ - expected: '?', found: 'X'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB char #8 differ - expected: '?', found: 'X'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB char #8 differ - expected: '?', found: 'X'
2 Halted 0 ms 0 KB -