Submission #116376

#	Time	Username	Problem	Language	Result	Execution time	Memory
116376		johutha	Paint By Numbers (IOI16_paint)	C++14	32 / 100	3 ms	384 KiB

paint

#include "paint.h"
#include <vector>
#include <iostream>

#include <cstdlib>

using namespace std;

void evaluate(const vector<int> &positions, const vector<pair<int,int>> &partititions, const vector<int> &c, int pos, vector<pair<bool,bool>> &res)
{
    vector<int> whites;
    whites.push_back(partititions[pos].first - 1);
    int curr = partititions[pos].first;
    for (int i = 0; i < (int)positions.size(); i++)
    {
        if (positions[i] == pos)
        {
            whites.push_back(curr + c[i]);
            curr += c[i] + 1;
        }
    }
    int movedist = partititions[pos].second - whites.back();
    curr = 0;
    if (movedist == 0)
    {
        int next = 1;
        for (int i = partititions[pos].first; i < partititions[pos].second; i++)
        {
            if (next < (int)whites.size() && whites[next] == i)
            {
                next++;
                res[i].second = true;
            }
            else
            {
                res[i].first = true;
            }
            
        }
        return;
    }
    for (int i = partititions[pos].first; i < partititions[pos].second; i++)
    {
        if (curr < (int)whites.size() - 1 && i >= whites[curr + 1]) curr++;
        res[i].first = true;
        if (i <= whites[curr] + movedist)
        {
            res[i].second = true;
        }
    }
}

string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
    int k = c.size();
    vector<pair<int,int>> partitions;
    vector<pair<bool,bool>> res(n, {false, false});
    vector<int> space;
    int lasts = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '_')
        {
            if (lasts != i)
            {
                partitions.push_back({lasts, i});
                space.push_back(i - lasts + 1);
            }
            lasts = i + 1;
        }
    }
    if (lasts != n)
    {
        partitions.push_back({lasts, n});
        space.push_back(n - lasts + 1);
    }
    vector<int> pos(k, -1);
    int p = partitions.size();
    int curr = p - 1;
    int i = k - 1;
    while (curr >= 0 && i >= 0)
    {
        if (space[curr] < c[i] + 1)
        {
            curr--;
        }
        else
        {
            space[curr] -= c[i] + 1;
            pos[i] = curr;
            i--;
        }
        
    }
    string out = s;
    curr = -1;
    for (int i = 0; i < k; i++)
    {
        if (curr < partitions[pos[i]].first) curr = partitions[pos[i]].first;
        else curr++;
        for (int j = 0; j < c[i]; j++)
        {
            out[curr] = 'X';
            curr++;
        }
    }
    evaluate(pos, partitions, c, 0, res);
    /*for (int i = 0; i < k; i++)
    {
        for (int next = pos[i] - 1; next >= 0; next--)
        {
            if (i > 0 && next < pos[i - 1]) break;
        }
    }*/
    string ns;
    for (int i = 0; i < n; i++)
    {
        if (s[i] != '.') ns.push_back(s[i]);
        else
        {
            if (res[i].first && res[i].second) ns.push_back('?');
            else if (res[i].first) ns.push_back('X');
            else ns.push_back('_');
        }
        
    }
    return ns;
}

• 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