Submission #239545

#	Time	Username	Problem	Language	Result	Execution time	Memory
239545		Ruxandra985	Paint By Numbers (IOI16_paint)	C++14	32 / 100	8 ms	512 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#define DIMN 200010
using namespace std;
int st[200010][110] , dr[200010][110] , sp0[DIMN] , sp1[DIMN];
char v[DIMN];
int white[DIMN] , black[DIMN];
pair <int,int> event[20000010];
string sol;


string solve_puzzle(string s, vector<int> c) {
    int n , k , i , j , ev , cnt , poz;

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

    for (i = 1 ; i <= n ; i++)
        v[i] = s[i - 1];

    for (i = 1 ; i <= n ; i++){
        sp0[i] = sp0[i - 1];
        sp1[i] = sp1[i - 1];

        if (s[i - 1] == '_')
            sp0[i]++;
        else if (s[i - 1] == 'X')
            sp1[i]++;
    }

    /// MAI SUNT NISTE CONDITII PT ALEA PRESTABILITE !!!!!!!!!


    st[0][0] = 1;
    /// st[i][j] = pot sa pun primele j seturi pe poz 1 .. i??
    for (i = 1 ; i <= n ; i++){
        st[i][0] = 1;
        for (j = 1 ; j <= k ; j++){
            st[i][j] = st[i - 1][j];

            /// altfel, inchei setul i pe pozitia j, DACA POT

            if (i - c[j - 1] - 1 == -1 && sp0[i] == 0 && v[i + 1] != 'X' && j == 1){
                st[i][j] = 1;
            }

            if (i - c[j - 1] - 1 >= 0 && v[i - c[j - 1]] != 'X' && sp0[i] - sp0[i - c[j - 1]] == 0 && v[i + 1] != 'X')
                st[i][j] = (st[i][j] | st[i - c[j - 1] - 1][j - 1]);


        }
    }

    dr[n + 1][k + 1] = 1;
    dr[n + 2][k + 1] = 1;
    /// dr[i][j] = pot sa pun seturile j ... k pe poz i ... n ?

    for (i = n ; i ; i--){
        dr[i][k + 1] = 1;
        for (j = k ; j ; j--){

            dr[i][j] = dr[i + 1][j];
            /// altfel, incep setul j pe pozitia i, daca pot

            if (i + c[j - 1] <= n+1 && v[i + c[j - 1]] != 'X' && sp0[i + c[j - 1]] - sp0[i - 1] == 0 && v[i - 1] != 'X')
                dr[i][j] = (dr[i][j] | dr[i + c[j - 1] + 1][j + 1]);


        }
    }

    ev = 0;

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

        for (j = 1 ; j <= k ; j++){

            /// poate sa se termine pe pozitia i setul j?

            if (i - c[j - 1] - 1 >= 0 && v[i - c[j - 1]] != 'X' && sp0[i] - sp0[i - c[j - 1]] == 0 && v[i + 1] != 'X'
                && st[i - c[j - 1] - 1][j - 1] && dr[i + 2][j + 1]){
                event[++ev] = make_pair(i - c[j - 1] + 1 , 1);
                event[++ev] = make_pair (i + 1 , -1);
            }
            else if (i - c[j - 1] == 0 && j == 1 && sp0[i] == 0 && v[i + 1] != 'X'){
                event[++ev] = make_pair(1 , 1);
                event[++ev] = make_pair(i + 1 , -1);
            }

            if ((st[i - 1][j] && dr[i + 1][j + 1]) || (st[i - 1][j - 1] && dr[i + 1][j]))
                white[i] = 1;

            //if (i == 7 && white[i] == 1)
              //  printf ("a");

        }

    }

    sort (event + 1 , event + ev + 1);

    cnt = 0;
    poz = 1;

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

        while (poz <= ev && event[poz].first == i){

            cnt += event[poz].second;
            poz++;

        }

        if (cnt)
            black[i] = 1;

    }


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

        if (v[i] != '.')
            sol.push_back(v[i]);
        else {

            if (black[i] && white[i])
                sol.push_back('?');
            else if (black[i])
                sol.push_back('X');
            else if (white[i])
                sol.push_back('_');

        }

    }

    return sol;
}

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