제출 #274501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
274501		stoyan_malinin	Paint By Numbers (IOI16_paint)	C++14	100 / 100	384 ms	45192 KiB

paint

#include "paint.h"
//#include "grader.cpp"

#include <vector>
#include <cstdlib>
#include <iostream>

using namespace std;

const int MAXK = 105;
const int MAXN = 2e5 + 5;

int n, k;
int pref[MAXN][3];

bool canBlack[MAXN];
bool dp1[MAXN][MAXK], dp2[MAXN][MAXK];

int convertSymbol(char c)
{
    if(c=='_') return 0;
    if(c=='X') return 1;
    if(c=='.') return 2;
}

int getSymbols(int l, int r, int c)
{
    l--;r--;
    if(l==-1 || l>r || l>=n) return 0;

    if(l==0) return pref[r][c];
    return pref[r][c] - pref[l-1][c];
}

void init(string &s, vector <int> &c)
{
    n = s.size();
    k = c.size() - 1;

    for(int i = 0;i<=n+3;i++)
    {
        canBlack[i] = false;
        pref[i][0] = pref[i][1] = pref[i][2] = 0;
        for(int j = 0;j<=k+3;j++) dp1[i][j] = dp2[i][j] = false;
    }

    pref[0][convertSymbol(s[0])]++;
    for(int i = 1;i<n;i++)
    {
        pref[i][0] = pref[i-1][0];
        pref[i][1] = pref[i-1][1];
        pref[i][2] = pref[i-1][2];
        pref[i][convertSymbol(s[i])]++;
    }
}

void fillDp1(string &s, vector <int> &c)
{
    for(int i = 1;i<=n;i++)
    {
        if(i<c[1]) continue;

        if(getSymbols(i-c[1]+1, i, 0)==0 && getSymbols(1, i-c[1], 1)==0) dp1[i][1] = true;
        if(getSymbols(i, i, 1)==0) dp1[i][1] |= dp1[i-1][1];
    }
    for(int i = 1;i<=n;i++)
    {
        for(int j = 2;j<=k;j++)
        {
            if(c[j]+1>=i) continue;

            if(getSymbols(i, i, 1)==0) dp1[i][j] |= dp1[i-1][j];
            if(getSymbols(i+1, i+1, 1)==0 && getSymbols(i-c[j]+1, i, 0)==0 && getSymbols(i-c[j], i-c[j], 1)==0)
            {
                dp1[i][j] |= dp1[ i - c[j] - 1 ][j-1];
            }
        }
    }
}

void markBlack(int l, int r)
{
    for(int i = l;i<=r;i++) canBlack[i] = true;
}

void fillDp2(string &s, vector <int> &c)
{
    for(int i = n;i>=1;i--)
    {
        if(n-i+1<c[k]) continue;

        if(getSymbols(i, i+c[k]-1, 0)==0 && getSymbols(i+c[k], n, 1)==0)
        {
            dp2[i][k] = true;

            if(k==1)
            {
                if(getSymbols(1, i-1, 1)==0) markBlack(i, i+c[k]-1);
            }
            else
            {
                if(i>2 && getSymbols(i-1, i-1, 1)==0 && dp1[i-2][k-1]==true) markBlack(i, i+c[k]-1);
            }
        }
        if(getSymbols(i, i, 1)==0) dp2[i][k] |= dp2[i+1][k];
    }
    for(int i = n;i>=1;i--)
    {
        for(int j = k-1;j>=1;j--)
        {
            if(c[j]+1>=n-i+1) continue;

            if(getSymbols(i, i, 1)==0) dp2[i][j] |= dp2[i+1][j];
            if(getSymbols(i-1, i-1, 1)==0 && getSymbols(i, i+c[j]-1, 0)==0 && getSymbols(i+c[j], i+c[j], 1)==0)
            {
                dp2[i][j] |= dp2[ i + c[j] + 1 ][j+1];
                if(dp2[ i + c[j] + 1 ][j+1]==true)
                {
                    if(j==1)
                    {
                        if(getSymbols(1, i-1, 1)==0) markBlack(i, i+c[j]-1);
                    }
                    else
                    {
                        if(i>2 && getSymbols(i-1, i-1, 1)==0 && dp1[i-2][j-1]==true) markBlack(i, i+c[j]-1);
                    }
                }
            }
        }
    }
}

bool completeString(string &s, vector <int> &c)
{
    init(s, c);
    fillDp1(s, c);
    fillDp2(s, c);

    /*
    for(int j = 1;j<k;j++)
    {
        for(int i = 1;i<=n-2;i++)
        {
            if(dp1[i][j]==true && getSymbols(i+1, i+1, 1)==0 && dp2[i+2][j+1]==true)
            {
                for(int p = i-c[j]+1;p<=i;p++) canBlack[p] = true;
            }
        }
    }

    for(int i = 1;i<=n;i++)
    {
        if(dp1[i][k]==true && getSymbols(i+1, n, 1)==0)
        {
            for(int p = i-c[k]+1;p<=i;p++) canBlack[p] = true;
        }
    }
    */

    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=k;j++)
        {
            //cout << "dp[" << i <<  "][" << j << "] = " << dp[i][j] << '\n';
        }
        //cout << '\n';
    }

    if(dp2[1][1]==1) return true;
    return false;
}

bool checkWhite(int ind)
{
    if(ind!=n && dp2[ind+1][1]==true && getSymbols(1, ind, 1)==0) return true;
    if(ind!=1 && dp1[ind-1][k]==true && getSymbols(ind, n, 1)==0) return true;

    if(ind!=1 && ind!=n)
    {
        for(int j = 2;j<=k;j++)
        {
            if(dp1[ind-1][j-1]==true && dp2[ind+1][j]==true) return true;
        }
    }

    return false;
}

bool checkBlack(int ind, vector <int> &c)
{
    return canBlack[ind];
}

string solve_puzzle(string s, vector<int> c)
{
    c.insert(c.begin(), -1);

    string answer;
    for(int i = 1;i<=s.size();i++) answer += "?";

    completeString(s, c);
    for(int i = 0;i<s.size();i++)
    {
        if(s[i]!='.')
        {
            answer[i] = s[i];
            continue;
        }

        bool white = false;
        if(checkWhite(i+1)==true) white = true;

        bool black = false;
        if(checkBlack(i+1, c)==true) black = true;

        if(white!=black)
        {
            if(white==true) answer[i] = '_';
            else if(black==true) answer[i] = 'X';
        }
    }


    return answer;
}
/*
..........
2
3 4

.X........
1
3

........
2
3 4

..._._....
1
3

X_X_X_X
2
1 1
*/

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:199:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |     for(int i = 1;i<=s.size();i++) answer += "?";
      |                   ~^~~~~~~~~~
paint.cpp:202:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |     for(int i = 0;i<s.size();i++)
      |                   ~^~~~~~~~~
paint.cpp: In function 'int convertSymbol(char)':
paint.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
   24 | }
      | ^

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10