제출 #274461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
274461		stoyan_malinin	Paint By Numbers (IOI16_paint)	C++14	7 / 100	1 ms	384 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 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++)
    {
        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 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(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];
            }
        }
    }
}

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

    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)
{
    if(k==1)
    {
        for(int i = ind;i<=min(ind+c[1]-1, n);i++)
        {
            if(i<c[1]) continue;
            if(getSymbols(ind, i, 0)!=0) break;

            //if(ind==3) cout << " -> " << i << '\n';

            if(getSymbols(1, i-c[1], 1)==0 && getSymbols(i-c[1]+1, i, 0)==0 && getSymbols(i+1, n, 1)==0) return true;
        }
        return false;
    }

    for(int i = ind;i<=min(ind+c[1]-1, n-2);i++)
    {
        if(i<c[1]) continue;
        if(getSymbols(1, ind, 0)==0 && getSymbols(i-c[1]+1, i, 0)==0 && dp2[i+2][2]==true) return true;
    }

    for(int j = 2;j<k;j++)
    {
        for(int i = ind;i<=min(ind+c[j]-1, n-2);i++)
        {
            if(i-c[j]-1<1) continue;
            if(getSymbols(ind, i, 0)!=0) break;

            if(getSymbols(i-c[j]+1, i, 0)==0 && dp1[ i - c[j] - 1 ][j]==true
               && getSymbols(i+1, i+1, 1)==0 && dp2[i+2][j+1]==true) return true;
        }
    }

    for(int i = ind;i<=min(ind+c[k]-1, n);i++)
    {
        if(i-c[k]-1<1) continue;
        if(getSymbols(ind, i, 0)!=0) break;

        if(getSymbols(i-c[k]+1, i, 0)==0 && dp1[ i - c[k] - 1 ][k-1]==true && getSymbols(i+1, n, 1)==0) return true;
    }

    return false;
}

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

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

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

        bool white = false;
        completeString(s, c);
        if(checkWhite(i+1)==true) white = true;

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

        //cout << i << " --> " << black << " " << white << '\n';

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

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