Submission #1054980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054980		ArthuroWich	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	348 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
string solve_puzzle(string s, vector<int> c) {
    int n = s.length();
    s = "@"+s;
    vector<int> pref(n+1, 0), x;
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i-1];
        if (s[i] == '_') {
            pref[i]++;
        }
        if (s[i] == 'X') {
            x.push_back(i-1);
        }
    }
    vector<pair<int, int>> segs(c.size());
    int i = 1, j = 0;
    while(i <= n && j < c.size()) {
        if (s[i] != '_' && pref[i+c[j]-1]-pref[i-1] == 0) {
            segs[j].first = i-1;
            i += c[j]+1;
            j++;
        } else {
            i++;
        }
    }
    i = n, j = c.size()-1;
    while(i > 0 && j >= 0) {
        if (s[i] != '_' && pref[i]-pref[i-c[j]] == 0) {
            segs[j].second = i-1;
            i -= c[j]+1;
            j--;
        } else {
            i--;
        }
    }
    string ans(n, '#');
    for (int i : x) {
        for (int j = 0; j < c.size(); j++) {
            if (segs[j].first <= i && i <= segs[j].second) {
                segs[j].second = min(i+c[j]-1, n-1);
                segs[j].first = max(i-c[j]+1, 0);
            }
        }
    }
    for (int i = 0; i < c.size(); i++) {
        for (int j = segs[i].first; j <= segs[i].second; j++) {
            ans[j] = '?';
        } 
        if (segs[i].first+c[i]-1 >= segs[i].second-c[i]+1) {
            for (int j = segs[i].second-c[i]+1; j <= segs[i].first+c[i]-1; j++) {
                ans[j] = 'X';
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (ans[i] == '#') {
            ans[i] = '_';
        }
        if (s[i+1] == '_') {
            ans[i] = '_';
        }
        if (s[i+1] == 'X') {
            ans[i] = 'X';
        }
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while(i <= n && j < c.size()) {
      |                     ~~^~~~~~~~~~
paint.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int j = 0; j < c.size(); j++) {
      |                         ~~^~~~~~~~~~
paint.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < c.size(); i++) {
      |                     ~~^~~~~~~~~~

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