Submission #116361

#	Time	Username	Problem	Language	Result	Execution time	Memory
116361		johutha	Paint By Numbers (IOI16_paint)	C++14	0 / 100	2 ms	256 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, string &res)
{
    vector<int> whites;
    whites.push_back(partititions[pos].first - 1);
    int curr = partititions[pos].first;
    for (int i = 0; i < 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;
    for (int i = partititions[pos].first; i < partititions[pos].second; i++)
    {
        if (curr < whites.size() - 1 && i >= whites[curr + 1]) curr++;
        if (i <= whites[curr] + movedist)
        {
            if (res[i] == '.') res[i] = '_';
            if (res[i] == 'X') res[i] = '?';
        }
        else
        {
            if (res[i] == '.') res[i] = 'X';
            if (res[i] == '_') res[i] = '?';
        }
    }
}

string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
    int k = c.size();
    vector<pair<int,int>> partitions;
    vector<int> space;
    string res = s;
    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 = res;
    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++;
        }
    }
    cout << out << "\n";
    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;
        }
    }*/
    return res;
}

Compilation message (stderr)

paint.cpp: In function 'void evaluate(const std::vector<int>&, const std::vector<std::pair<int, int> >&, const std::vector<int>&, int, std::__cxx11::string&)':
paint.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < positions.size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~
paint.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (curr < whites.size() - 1 && i >= whites[curr + 1]) curr++;
             ~~~~~^~~~~~~~~~~~~~~~~~~

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