Submission #395030

#	Time	Username	Problem	Language	Result	Execution time	Memory
395030		idk321	Paint By Numbers (IOI16_paint)	C++11	90 / 100	294 ms	524292 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

std::string solve_puzzle(std::string s, std::vector<int> c) {

    string res = s;

    if (s.size() == 1)
    {
        if (s != ".") return s;
        return "X";
    }

    vector<int> type;
    type.push_back(0);
    for (int i = 0;  i< c.size(); i++)
    {
        for (int j = 0; j < c[i]; j++)
        {
            int cur = 1;
            if (j == c[i] - 1) cur *= 2;
            if (j == 0) cur *= 3;
            type.push_back(cur);
        }
        type.push_back(0);
    }

    int n = s.size();
    vector<vector<bool>> right(n, vector<bool>(type.size()));
    if (s[0] == 'X')
    {
        right[0][1] = true;
    } else if (s[0] == '_')
    {
        right[0][0] = true;
    } else
    {
        right[0][0] = true;
        right[0][1] = true;
    }




    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < right[i - 1].size(); j++)
        {
            if (right[i - 1][j])
            {
                if (type[j] == 0)
                {
                    if (s[i] == 'X')
                    {
                        if (j + 1 != type.size()) right[i][j + 1] = true;
                    } else if (s[i] == '_')
                    {
                        right[i][j] = true;
                    } else
                    {
                        if (j + 1 != type.size()) right[i][j + 1] = true;
                        right[i][j] = true;
                    }
                } else if (type[j] % 2 == 0)
                {
                    if (s[i] == 'X')
                    {

                    } else if (s[i] == '_')
                    {
                        right[i][j + 1] = true;
                    } else
                    {

                        right[i][j + 1] = true;
                    }
                } else
                {
                    if (s[i] == 'X')
                    {
                        right[i][j + 1] = true;
                    } else if (s[i] == '_')
                    {

                    } else
                    {

                        right[i][j + 1] = true;
                    }
                }
            }
        }
    }

    vector<vector<bool>> left(n, vector<bool>(type.size()));
    if (s[n - 1] == 'X')
    {
        left[n - 1][type.size() - 2] = true;
    } else if (s[n - 1] == '_')
    {
        left[n - 1][type.size() - 1] = true;
    } else
    {
        left[n - 1][type.size() - 1] = true;
        left[n - 1][type.size() - 2] = true;
    }



    for (int i = n - 2; i >= 0; i--)
    {
        for (int j = 0; j < right[i + 1].size(); j++)
        {
            if (left[i + 1][j])
            {
                if (type[j] == 0)
                {
                    if (s[i] == 'X')
                    {
                        if (j - 1 >= 0) left[i][j - 1] = true;
                    } else if (s[i] == '_')
                    {
                        left[i][j] = true;
                    } else
                    {
                        if (j - 1 >= 0) left[i][j - 1] = true;
                        left[i][j] = true;
                    }
                } else if (type[j] % 3 == 0)
                {
                    if (s[i] == 'X')
                    {

                    } else if (s[i] == '_')
                    {
                        left[i][j - 1] = true;
                    } else
                    {

                        left[i][j - 1] = true;
                    }
                } else
                {
                    if (s[i] == 'X')
                    {
                        //if (i == 2) cout << "Oj " << " "<< type[j]<< " " << type[j - 1]<< " " <<j <<endl;
                        left[i][j - 1] = true;
                    } else if (s[i] == '_')
                    {

                    } else
                    {

                        left[i][j - 1] = true;
                    }
                }
            }
        }
    }






    vector<bool> poss1(n);

    vector<bool> poss2(n);
    for (int i = 0; i < n; i++)
    {

        for (int j = 0; j < type.size(); j++)
        {
            if (left[i][j] && right[i][j])
            {
                if (type[j] == 0) poss1[i] = true;
                else poss2[i] = true;
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (poss2[i] && poss1[i])
        {
            res[i] = '?';
        } else if (poss2[i]) res[i] = 'X';
        else res[i] = '_';
    }

    /*
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < type.size(); j++)
        {
            if (right[i][j]) cout << i << " "<< j << endl;
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < type.size(); j++)
        {
            if (left[i][j]) cout << i << " "<< j << " " << type[j] << endl;
        }
    } */
    return res;
}

/*
..X._..X.
3 2 1 2
*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0;  i< c.size(); i++)
      |                      ~^~~~~~~~~~
paint.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int j = 0; j < right[i - 1].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
paint.cpp:59:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                         if (j + 1 != type.size()) right[i][j + 1] = true;
      |                             ~~~~~~^~~~~~~~~~~~~~
paint.cpp:65:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                         if (j + 1 != type.size()) right[i][j + 1] = true;
      |                             ~~~~~~^~~~~~~~~~~~~~
paint.cpp:116:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for (int j = 0; j < right[i + 1].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
paint.cpp:176:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         for (int j = 0; j < type.size(); j++)
      |                         ~~^~~~~~~~~~~~~

• 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: 0 / 10