Submission #242437

#	Time	Username	Problem	Language	Result	Execution time	Memory
242437		Coroian_David	Paint By Numbers (IOI16_paint)	C++11	100 / 100	314 ms	84020 KiB

paint

#include <bits/stdc++.h>

//#include "paint.h"

#define MAX_N 200000
#define MAX_K 100

using namespace std;

string x;

int n, k;

string rez;

int v[MAX_K + 1];
int dp[MAX_N + 2 + 1][MAX_K + 1];
int pos[MAX_N + 2 + 1][2];

int b[MAX_N + 1];
int w[MAX_N + 1];

void getSum()
{
    for(int i = 1; i <= n; i ++)
    {
        b[i] = b[i - 1] + (x[i] == 'X');
        w[i] = w[i - 1] + (x[i] == '_');
    }
}

void getDp()
{
    dp[1][0] = 1;

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 0; j <= k; j ++)
        {
            if(dp[i][j] == 1)
            {
                //cout << "SUNTEM " << i << " POS " << j << "\n";

                if(x[i] != 'X')
                    dp[i + 1][j] = 1;//white

                if(j < k)
                {
                    int urm = i + v[j + 1] - 1;
                    int y = w[urm] - w[i - 1];
                    if(y == 0)
                    {
                        if(urm == n || (urm < n && x[urm + 1] != 'X'))
                            dp[urm + 2][j + 1] = 1;
                    }
                }
            }
        }
    }
}

void getPos()
{
    dp[n + 1][k] <<= 1;
    dp[n + 2][k] <<= 1;

    for(int i = n; i >= 1; i --)
    {
        for(int j = 0; j <= k; j ++)
        {
            if(dp[i][j] == 1)
            {
                if(x[i] != 'X' && dp[i + 1][j] == 2)
                {
                    dp[i][j] = 2;//white
                    pos[i][0] = 1;
                    //cout << " " << i << " POATE FI ALB \n";
                }

                if(j < k)
                {
                    int urm = i + v[j + 1] - 1;
                    int y = w[urm] - w[i - 1];
                    if(y == 0)
                    {
                        if(urm == n || (urm < n && x[urm + 1] != 'X'))
                        if(dp[urm + 2][j + 1] == 2)
                        {
                            dp[i][j] = 2;
                            pos[i][1] ++;
                            pos[urm + 1][1] --;
                            pos[urm + 1][0] = 1;

                            //cout << " DE LA  " << i << " LA " << urm << " NEGRU \n";
                        }
                    }
                }
            }
        }
    }

}

void getRez()
{
    rez.resize(n);
    for(int i = 1; i <= n; i ++)
    {
        pos[i][1] += pos[i - 1][1];

        if(pos[i][0] != 0 && pos[i][1] != 0)
            rez[i - 1] = '?';

        else
            if(pos[i][0] != 0)
                rez[i - 1] = '_';

        else
            rez[i - 1] = 'X';
    }
}

string solve_puzzle(string s, vector<int> c)
{
    n = s.size();
    k = c.size();

    s = " " + s;
    x = s;
    for(int i = 0; i < k; i ++)
        v[i + 1] = c[i];

    getSum();

    getDp();

    getPos();

    getRez();

    return rez;
}

• 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