Submission #1000350

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

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

#define str string
#define print(a) for(auto x : a) cout << x << ' '; cout << endl;

str solve_puzzle(str s, vector<int> c) {
    int left = 0, right = 0, n = (int)s.size(), k = (int)c.size();
    vector<int> start;
    while(right < n and start.size() < k){
        int sz = start.size();
        while(right < n and s[right] == '.'){
            right ++;
            if(right - left == c[start.size()]){
                start.push_back(left);
                right ++;
                left = right;
                break;
            }
        }
        if(sz != start.size())
            continue;
        right ++;
        left = right;
    }
    vector<int> start_rev;
    right = n - 1;
    left = n - 1;
    while(right >= 0 and start_rev.size() < k){
        int sz = start_rev.size();
        while(right >= 0 and s[right] == '.'){
            right --;
            if(left - right == c[k - 1 - start_rev.size()]){
                start_rev.push_back(right + 1);
                right --;
                left = right;
                break;
            }
        }
        if(sz != start_rev.size())
            continue;
        right --;
        left = right;
    }
    reverse(start_rev.begin(), start_rev.end());
    vector<str> p(k);
    for(int i = 0; i < k; i ++){
        p[i] = s;
        for(int j = 0; j < i; j ++)
            for(int x = 0; x < c[j]; x ++)
                p[i][x + start[j]] = 'X';
        for(int j = k - 1; j >= i + 1; j --)
            for(int x = 0; x < c[j]; x ++)
                p[i][x + start_rev[j]] = 'X';
    }
    str ans = s;
    for(int i = 0; i < k; i ++){
        for(int j = (i - 1 < 0 ? -1 : start[i - 1]) + (i - 1 < 0 ? 0 : c[i - 1]) + 1; j <= start_rev[i]; j ++){
            bool flag = 1;
            for(int x = 0; x < c[i]; x ++){
                if(s[x + j] != '.'){
                    flag = 0;
                    break;
                }
            }
            if(flag){
                for(int x = 0; x < c[i]; x ++)
                    p[i][j + x] = 'X';
                for(int x = 0; x < n; x ++){
                    if(s[x] == '.'){
                        if(p[i][x] == 'X'){
                            if(ans[x] == '.' or ans[x] == 'X')
                                ans[x] = 'X';
                            else
                                ans[x] = '?';
                        }
                        else{
                            if(ans[x] == '.' or ans[x] == '_')
                                ans[x] = '_';
                            else
                                ans[x] = '?';
                        }
                    }
                }
                for(int x = 0; x < c[i]; x ++)
                    p[i][j + x] = '.';
            }
        }
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:11:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |     while(right < n and start.size() < k){
      |                         ~~~~~~~~~~~~~^~~
paint.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         if(sz != start.size())
      |            ~~~^~~~~~~~~~~~~~~
paint.cpp:30:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |     while(right >= 0 and start_rev.size() < k){
      |                          ~~~~~~~~~~~~~~~~~^~~
paint.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if(sz != start_rev.size())
      |            ~~~^~~~~~~~~~~~~~~~~~~

• 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