Submission #284641

#	Time	Username	Problem	Language	Result	Execution time	Memory
284641		A02	Paint By Numbers (IOI16_paint)	C++14	90 / 100	543 ms	524292 KiB

paint

#include "paint.h"
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;

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

    int n = s.size();
    int k = c.size();

    int first_left_black = n;
    for (int i = 0; i < n; i++){
        if (s[i] == 'X'){
            first_left_black = i;
            break;
        }
    }
    int first_right_black = -1;
    for (int i = n - 1; i >= 0; i--){
        if (s[i] == 'X'){
            first_right_black = i;
            break;
        }
    }

    vector<vector<vector<int> > > DP_left_K (n, vector<vector<int> > (k, vector<int>()));
    vector<vector<vector<int> > > DP_right_K (n, vector<vector<int> > (k, vector<int>()));


    if (s[0] != '_'){
        DP_left_K[0][0].push_back(1);
    }

    for (int N = 1; N < n; N++){

        for (int K = 0; K < k; K++){
            //cout << N << ' ' << K << endl;
            if (s[N] != '_'){
                if (K == 0 && N <= first_left_black){
                    DP_left_K[N][K].push_back(1);
                }
                if (K > 0 && DP_left_K[N-1][K-1].size() > 0 && DP_left_K[N - 1][K - 1][DP_left_K[N - 1][K - 1].size() - 1] >= c[K - 1] + 1){
                    DP_left_K[N][K].push_back(1);
                }
                for (int i = 0; i < DP_left_K[N - 1][K].size(); i++){
                    if (DP_left_K[N - 1][K][i] + 1 > c[K]){
                        break;
                    }
                    DP_left_K[N][K].push_back(DP_left_K[N - 1][K][i] + 1);
                }
            }
            //cout << 'x' << endl;
            if (s[N] != 'X'){

                if (DP_left_K[N-1][K].size() > 0 && DP_left_K[N - 1][K][DP_left_K[N - 1][K].size() - 1] >= c[K]){
                    DP_left_K[N][K].push_back(DP_left_K[N - 1][K][DP_left_K[N - 1][K].size() - 1] + 1);
                }

            }

        }

    }

    if (s[n-1] != '_'){
        DP_right_K[n-1][k-1].push_back(1);
    }

    for (int N = n - 2; N >= 0; N--){

        for (int K = k - 1; K >= 0; K--){
            if (s[N] != '_'){
                if (K == k - 1 && N >= first_right_black){
                    DP_right_K[N][K].push_back(1);
                }
                if (K < k - 1 && DP_right_K[N+1][K+1].size() > 0 && DP_right_K[N + 1][K + 1][DP_right_K[N + 1][K + 1].size() - 1] >= c[K + 1] + 1){
                    DP_right_K[N][K].push_back(1);
                }
                for (int i = 0; i < DP_right_K[N + 1][K].size(); i++){
                    if (DP_right_K[N + 1][K][i] + 1 > c[K]){
                        break;
                    }
                    DP_right_K[N][K].push_back(DP_right_K[N + 1][K][i] + 1);
                }
            }
            //cout << 'x' << endl;
            if (s[N] != 'X'){

                if (DP_right_K[N+1][K].size() > 0 && DP_right_K[N + 1][K][DP_right_K[N + 1][K].size() - 1] >= c[K]){
                    DP_right_K[N][K].push_back(DP_right_K[N + 1][K][DP_right_K[N + 1][K].size() - 1] + 1);
                }

            }

        }

    }


//    for (int N = 0; N < n; N++){
//
//        for (int K = 0; K < k; K++){
//            cout << N << ':' << K << endl << "left" << endl;
//            for (int i = 0; i < DP_left_K[N][K].size(); i++){
//                cout << DP_left_K[N][K][i] << ' ';
//            }
//            cout << endl << "right" << endl;
//            for (int i = 0; i < DP_right_K[N][K].size(); i++){
//                cout << DP_right_K[N][K][i] << ' ';
//            }
//            cout << endl << endl;
//
//        }
//    }

    string result = s;

    for (int i = 0; i < n; i++){
        if (s[i] == '.'){

            bool can_be_black = false;
            bool can_be_white = false;

            if (i < first_left_black){
                if (DP_right_K[i][0].size() > 0 && DP_right_K[i][0][DP_right_K[i][0].size() - 1] > c[0]){
                    can_be_white = true;
                }
            }
            if (i > first_right_black){
                if (DP_left_K[i][k - 1].size() > 0 && DP_left_K[i][k - 1][DP_left_K[i][k - 1].size() - 1] > c[k - 1]){
                    can_be_white = true;
                }
            }

            for (int K = 0; K < k - 1; K++){

                if (DP_left_K[i][K].size() > 0 && DP_right_K[i][K + 1].size() > 0){
                    if (DP_left_K[i][K][DP_left_K[i][K].size() - 1] > c[K] && DP_right_K[i][K + 1][DP_right_K[i][K + 1].size() - 1] > c[K + 1]){
                        can_be_white = true;
                    }
                }
            }

            for (int K = 0; K < k; K++){
                //cout << 'p' << i << ' ' << K << endl;
                if (DP_left_K[i][K].size() > 0 && DP_right_K[i][K].size() > 0){

                    int left_pointer = 0;
                    int right_pointer = DP_right_K[i][K].size() - 1;

                    while (left_pointer < DP_left_K[i][K].size() && right_pointer >= 0){
                        //cout << ' ' << DP_left_K[i][K][left_pointer] << ' ' << DP_right_K[i][K][right_pointer] << ' ' << c[K] << endl;
                        if (DP_left_K[i][K][left_pointer] + DP_right_K[i][K][right_pointer] == c[K] + 1){
                            can_be_black = true;
                            break;
                        }
                        if (DP_left_K[i][K][left_pointer] + DP_right_K[i][K][right_pointer] > c[K] + 1){
                            right_pointer--;
                        }
                        if (DP_left_K[i][K][left_pointer] + DP_right_K[i][K][right_pointer] < c[K] + 1){
                            left_pointer++;
                        }
                    }


                }

            }

            if (can_be_black && can_be_white){
                result[i] = '?';
            } else {
                if (can_be_black){
                    result[i] = 'X';
                } else {
                    result[i] = '_';
                }
            }

        }
    }

    return result;

}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:49:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                 for (int i = 0; i < DP_left_K[N - 1][K].size(); i++){
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:83:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |                 for (int i = 0; i < DP_right_K[N + 1][K].size(); i++){
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:155:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |                     while (left_pointer < DP_left_K[i][K].size() && right_pointer >= 0){
      |                            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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