Submission #272429

#	Time	Username	Problem	Language	Result	Execution time	Memory
272429		stoyan_malinin	Paint By Numbers (IOI16_paint)	C++14	10 / 100	10 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 dp[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] = 0;
        for(int j = 0;j<=k+3;j++) dp[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][convertSymbol(s[i])]++;
    }
}

bool completeString(string &s, vector <int> &c)
{
    init(s, c);
    //cout << s << " " << k << '\n';

    for(int i = 1;i<=n;i++)
    {
        if(i<c[1]) continue;

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

            if(getSymbols(i, i, 1)==0) dp[i][j] |= dp[i-1][j];

            //if(i==8 && j==2) cout << getSymbols(i+1, i+1, 1) << " " << getSymbols(i-c[j]+1, i, 0) << '\n';
            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)
            {
                //if(i==8 && j==2) cout << "gut " << dp[ i - c[j] - 1 ][j-1] << " " << c[j] << '\n';
                dp[i][j] |= dp[ i - c[j] - 1 ][j-1];
            }
        }
    }

    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(dp[n][k]==1) 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;
        }

        s[i] = '_';
        bool white = false;
        if(completeString(s, c)==true) white = true;

        s[i] = 'X';
        bool black = false;
        if(completeString(s, 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
*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i = 1;i<=s.size();i++) answer += "?";
      |                   ~^~~~~~~~~~
paint.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     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: 3 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10