Submission #239985

#	Time	Username	Problem	Language	Result	Execution time	Memory
239985		nicolaalexandra	Paint By Numbers (IOI16_paint)	C++14	100 / 100	879 ms	177072 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#define DIM 400010
#define DIMK 110
using namespace std;

int sp[DIM*2],sp2[DIM*2],aib[DIM],dp_left[DIM][DIMK],dp_right[DIM][DIMK];
int f[DIM],f2[DIM];

int get_sum (int x, int y){
    if (x > y)
        return 0;
    int sol = sp[y];
    if (x)
        sol -= sp[x-1];
    return sol;
}

int get_sum2 (int x, int y){
    if (x > y)
        return 0;
    int sol = sp2[y];
    if (x)
        sol -= sp2[x-1];
    return sol;
}

void update (int p, int n, int val){
    for (;p<=n;p+=(p&-p))
        aib[p] += val;
}

int query (int p){
    int sol = 0;
    for (;p;p-=(p&-p))
        sol += aib[p];
    return sol;
}

string solve_puzzle (string S, vector <int> c){

    int n = S.length(), i, j;
    string s = " ";
    for (i=1;i<=n;i++)
        s.push_back(S[i-1]);

    for (i=1;i<=n;i++){
        sp[i] = sp[i-1], sp2[i] = sp2[i-1];
        if (s[i] == '_')
            sp[i]++;
        if (s[i] == 'X')
            sp2[i]++;
    }

    /// dp_left[i][j] = true daca pot sa pun primele j piese pe primele i pozitii

    for (j=0;j<c.size();j++){
        int lg = c[j];

        for (i=lg;i<=n;i++){

            if (!j){

                if (s[i] == '_')
                    dp_left[i][j] = dp_left[i-1][j];
                else {
                    if (s[i] == 'X'){
                        if (get_sum(i-lg+1,i) == 0 && get_sum2(1,i-lg) == 0)
                            dp_left[i][j] = 1;
                    } else {
                        dp_left[i][j] = dp_left[i-1][j];
                        if (get_sum(i-lg+1,i) == 0 && get_sum2(1,i-lg) == 0)
                            dp_left[i][j] = 1;
                    }}

                continue;
            }

            if (s[i] == '_')
                dp_left[i][j] = dp_left[i-1][j];
            else {
                if (s[i] == 'X'){
                    if (get_sum(i-lg+1,i) == 0 && s[i-lg] != 'X')
                        dp_left[i][j] = dp_left[i-lg-1][j-1];
                } else { /// '.'
                    dp_left[i][j] = dp_left[i-1][j];
                    if (get_sum(i-lg+1,i) == 0 && s[i-lg] != 'X')
                        dp_left[i][j] |= dp_left[i-lg-1][j-1];
                }}}}

    for (j=c.size()-1;j>=0;j--){
        int lg = c[j];

        for (i=n-lg+1;i>=1;i--){
            if (j == c.size()-1){
                if (s[i] == '_')
                    dp_right[i][j] = dp_right[i+1][j];
                else{
                    if (s[i] == 'X'){
                        if (get_sum(i,i+lg-1) == 0 && get_sum2(i+lg,n) == 0)
                            dp_right[i][j] = 1;
                    } else {
                        dp_right[i][j] = dp_right[i+1][j];
                        if (get_sum(i,i+lg-1) == 0 && get_sum2(i+lg,n) == 0)
                            dp_right[i][j] = 1;
                    }}
                continue;
            }

            if (s[i] == '_')
                dp_right[i][j] = dp_right[i+1][j];
            else{
                if (s[i] == 'X'){
                    if (get_sum(i,i+lg-1) == 0 && s[i+lg] != 'X')
                        dp_right[i][j] = dp_right[i+lg+1][j+1];
                } else {
                    dp_right[i][j] = dp_right[i+1][j];
                    if (get_sum(i,i+lg-1) == 0 && s[i+lg] != 'X')
                        dp_right[i][j] |= dp_right[i+lg+1][j+1];
                }}}}

    /// f[i] = 1 => casuta asta nu poate sa fie mereu alba

    for (i=1;i<=n;i++){
        if (s[i] == '_')
            continue;

        /// incerc sa pun X aici si sa vad daca pot sa am vreo solutie
        if (s[i-1] == 'X')
            continue;

        int maxi = 0;
        for (j=0;j<c.size() && c.size() > 1;j++){
            int lg = c[j];
            if (get_sum(i,i+lg-1) || (i-2 < 0 && j) || i + lg - 1 > n)
                continue;
            if (s[i+lg] == 'X')
                continue;

            if (!j && get_sum2(1,i-1) == 0 && (c.size()==1 || dp_right[i+lg+1][j+1]))
                maxi = max (maxi,lg);

            if (j == c.size()-1 && get_sum2(i+lg,n) == 0 && (c.size()==1 || dp_left[i-2][j-1]))
                maxi = max (maxi,lg);

            if (dp_left[i-2][j-1] && dp_right[i+lg+1][j+1])
                maxi = max (maxi,lg);
        }

        if (c.size() == 1 && get_sum2(1,i-1) == 0 && get_sum2 (i+c[0],n) == 0 && get_sum(i,i+c[0]-1) == 0 && i+c[0]-1 <= n)
            maxi = c[0];

        /// in intervalul i...i+maxi-1 nu pot avea mereu alb
        for (j=i;j<=i+maxi-1;j++)
            f[j] = 1;
    }

    /// f2[i] = 1 -> casuta asta nu poate sa fie neagra mereu

    for (i=1;i<=n;i++){
        int ok = 0;
        for (j=0;j<c.size();j++){
            if (!j && dp_right[i+1][j] && get_sum2(1,i) == 0){
                ok = 1;
                break;
            }
            if (j == c.size()-1 && dp_left[i-1][j] && get_sum2(i,n) == 0){
                ok = 1;
                break;
            }
            if (dp_left[i-1][j] && dp_right[i+1][j+1]){
                ok = 1;
                break;
            }}

        f2[i] = ok;
    }


    for (i=1;i<=n;i++){
        if (s[i] == 'X' || s[i] == '_')
            continue;
        if (f[i] == 0 && f2[i] == 1){
            s[i] = '_';
            continue;
        }
        if (f[i] == 1 && f2[i] == 0){
            s[i] = 'X';
            continue;
        }
        s[i] = '?';
    }

    string sol = "";
    for (i=1;i<=n;i++)
        sol.push_back(s[i]);

    return sol;

}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j=0;j<c.size();j++){
              ~^~~~~~~~~
paint.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (j == c.size()-1){
                 ~~^~~~~~~~~~~~~
paint.cpp:133:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=0;j<c.size() && c.size() > 1;j++){
                  ~^~~~~~~~~
paint.cpp:143:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (j == c.size()-1 && get_sum2(i+lg,n) == 0 && (c.size()==1 || dp_left[i-2][j-1]))
                 ~~^~~~~~~~~~~~~
paint.cpp:162:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=0;j<c.size();j++){
                  ~^~~~~~~~~
paint.cpp:167:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (j == c.size()-1 && dp_left[i-1][j] && get_sum2(i,n) == 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: 10 / 10