Submission #337086

#	Time	Username	Problem	Language	Result	Execution time	Memory
337086		blue	Paint By Numbers (IOI16_paint)	C++11	0 / 100	1 ms	1152 KiB

paint

#include "paint.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> G(2e5);

string solve_puzzle(string s, vector<int> c)
{
//THE STRING IS ONE-INDEXED, THE BLOCKS ARE ZERO-INDEXED

    int n = s.size();
    s = "!" + s;

    vector<int> blacksum(n+1);
    blacksum[0] = 0;
    for(int i = 1; i <= n; i++) blacksum[i] = blacksum[i-1] + (s[i] == 'X');

    vector<int> whitesum(n+1);
    whitesum[0] = 0;
    for(int i = 1; i <= n; i++) whitesum[i] = whitesum[i-1] + (s[i] == '_');

    vector<int> psblwhite(n+1, 0);
    vector<int> psblblack(n+1, 0);

    int k = c.size();
    vector<int> pos(k); //rightmost position of the block

    pos.push_back(n+1);
    c.push_back(1);

    for(pos[0] = c[0]; whitesum[pos[0]] - whitesum[pos[0] - c[0]] != 0; pos[0]++);

    for(int j = 1; j < k; j++)
    {
        for(pos[j] = pos[j-1] + c[j] + 1; whitesum[pos[j]] - whitesum[pos[j] - c[j]] != 0; pos[j]++);
    }

    for(int j = k-1; j >= 0; j--)
    {
        while(whitesum[pos[j]] - whitesum[pos[j] - c[j]] != 0
           || blacksum[pos[j+1] - c[j+1]] - blacksum[pos[j]] != 0
           || s[pos[j] - c[j]] == 'X')
                pos[j]++;
    }

    for(int i = 1; i <= pos[0] - c[0]; i++) psblwhite[i] = 1;

    for(int j = 0; j < k; j++)
    {
        for(int i = pos[j] - c[j] + 1; i <= pos[j]; i++) psblblack[i] = 1;
        for(int i = pos[j] + 1; i <= pos[j+1] - c[j+1]; i++) psblwhite[i] = 1;
    }

    for(int i = 1; i <= n; i++) cout << psblwhite[i];
    cout << '\n';

    return "?";
}

• 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