Submission #773517

#	Time	Username	Problem	Language	Result	Execution time	Memory
773517		peteza	Paint By Numbers (IOI16_paint)	C++14	32 / 100	1 ms	468 KiB

paint

//BRUH

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

int wc[200005] = {}, bc[200005] = {};
int lb[200005] = {}, rb[200005] = {};
bool black[200005] = {}, white[200005] = {};
bool dpl[200005][105] = {}, dpr[200005][105] = {}; //possible to do from left? possible to do from right? blablabla
int qsl[2000005][105] = {}, qsr[200005][105] = {};
int final[200005] = {};

std::string solve_puzzle(std::string s, std::vector<int> c) {
    lb[0] = 0; for(int i=1;i<s.size();i++) lb[i] = (s[i] == 'X' ? i : lb[i-1]);
    rb[s.size()-1] = s.size()-1;
    for(int i=s.size()-2;i>=0;i--) rb[i] = (s[i] == 'X' ? i : rb[i+1]);
    wc[0] = (s[0] == '_'); bc[0] = (s[0] == 'X');
    for(int i=1;i<s.size();i++) wc[i] = wc[i-1] + (s[i] == '_'), bc[i] = bc[i-1] + (s[i] == 'X');
    bc[s.size()] = bc[s.size()-1];
    auto getwc = [&](int a, int b){return wc[b] - (a == 0 ? 0 : wc[a-1]);};
    auto getbc = [&](int a, int b){return (b < 0 ? bc[0] : bc[b]) - (a == 0 ? 0 : bc[a-1]);};

    
    for(int i=0;i<s.size();i++) black[i] = (s[i] == 'X'), white[i] = (s[i] == '_');

    auto getqsl = [&](int a, int b, int lev){return qsl[b][lev] - (a == 0 ? 0 : qsl[a-1][lev]);};
    auto getqsr = [&](int a, int b, int lev){return qsr[a][lev] - (b == s.size()-1 ? 0 : qsr[b+1][lev]);};
    
    for(int i=0;i<s.size();i++) {
        if(i+1 >= c[0] && getwc(i-c[0]+1, i) == 0 && !getbc(0, i-c[0]) && !(c.size() == 1 && getbc(i+1, s.size()-1))) dpl[i][0] = 1;
        else dpl[i][0] = 0;
        qsl[i][0] = dpl[i][0] + (i == 0 ? 0 : qsl[i-1][0]);
    }
    for(int j=1;j<c.size();j++) {
        for(int i=0;i<s.size();i++) {
            if(i > c[j] && getwc(i-c[j]+1, i) == 0 && s[i-c[j]] != 'X' && getqsl(lb[i-c[j]-1], i-c[j]-1, j-1) && !(c.size() == j+1 && getbc(i+1, s.size()-1))) dpl[i][j] = 1;
            else dpl[i][j] = 0;
            qsl[i][j] = dpl[i][j] + (i == 0 ? 0 : qsl[i-1][j]);
            //std::cout << i;
        }
    }
    for(int i=s.size()-1;i>=0;i--) {
        if(i+c[c.size()-1] <= s.size() && getwc(i, i+c[c.size()-1]-1) == 0 && !getbc(i+c[c.size()-1], s.size()-1) && !(c.size() == 1 && getbc(0, i-1))) dpr[i][c.size()-1] = 1;
        else dpr[i][c.size()-1] = 0;
        qsr[i][c.size()-1] = dpr[i][c.size()-1] + (i == s.size()-1 ? 0 : qsr[i+1][c.size()-1]);
    }
    for(int j=c.size()-2;j>=0;j--) {
        for(int i=s.size()-1;i>=0;i--) {
            if(i+c[j]+2 <= s.size() && getwc(i, i+c[j]-1) == 0 && s[i+c[j]] != 'X' && getqsr(i+c[j]+1, rb[i+c[j]+1], j+1) && !(!j && getbc(0, i-1))) dpr[i][j] = 1;
            else dpr[i][j] = 0;
            qsr[i][j] = dpr[i][j] + (i == s.size()-1 ? 0 : qsr[i+1][j]);
        }
    }
    //for(int i=0;i<s.size();i++) std::cout << dpl[i][0]; std::cout << '\n';
    //for(int i=0;i<s.size();i++) std::cout << dpr[i][0]; std::cout << '\n';
    for(int i=0;i+1<s.size();i++)
        if(qsr[i+1][0]) white[i] = 1;
    for(int i=1;i<s.size();i++)
        if(qsl[i-1][c.size()-1]) white[i] = 1;
    for(int i=0;i+2<s.size();i++) {
        for(int j=0;j+1<c.size();j++) {
            if(getqsl(0, i, j) && getqsr(i+2, s.size()-1, j+1))
                white[i+1] = 1;
        }
    }
    for(int j=0;j<c.size();j++) {
        if(j == c.size()-1) {
            for(int i=0;i<s.size();i++) {
                if(dpl[i][j])
                    final[i-c[j]+1] = 1, final[i+1] = -1;
            }
        } else {
            for(int i=0;i+2<s.size();i++) {
                if(dpl[i][j] && qsr[i+2][j+1]) //doable 
                    final[i-c[j]+1] = 1, final[i+1] = -1;
            }
        }
    }
    int cnt = 0;
    for(int i=0;i<s.size();i++) {
        cnt += final[i];
        black[i] = cnt;
    }
    std::string ans = s;
    for(int i=0;i<s.size();i++) {
        if(black[i] && white[i]) ans[i] = '?';
        else if(black[i]) ans[i] = 'X';
        else ans[i] = '_';
    }
    return ans;
}
/*
#include <cassert>
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];

int main() {
    assert(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(1 == scanf("%d", &c[i]));
    }
    std::string ans = solve_puzzle(s, c);

    printf("%s\n", ans.data());
    return 0;
}
*/
/*
........
2
3 4
*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:15:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     lb[0] = 0; for(int i=1;i<s.size();i++) lb[i] = (s[i] == 'X' ? i : lb[i-1]);
      |                            ~^~~~~~~~~
paint.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=1;i<s.size();i++) wc[i] = wc[i-1] + (s[i] == '_'), bc[i] = bc[i-1] + (s[i] == 'X');
      |                 ~^~~~~~~~~
paint.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<s.size();i++) black[i] = (s[i] == 'X'), white[i] = (s[i] == '_');
      |                 ~^~~~~~~~~
paint.cpp: In lambda function:
paint.cpp:28:70: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     auto getqsr = [&](int a, int b, int lev){return qsr[a][lev] - (b == s.size()-1 ? 0 : qsr[b+1][lev]);};
      |                                                                    ~~^~~~~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<s.size();i++) {
      |                 ~^~~~~~~~~
paint.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int j=1;j<c.size();j++) {
      |                 ~^~~~~~~~~
paint.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i=0;i<s.size();i++) {
      |                     ~^~~~~~~~~
paint.cpp:37:125: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |             if(i > c[j] && getwc(i-c[j]+1, i) == 0 && s[i-c[j]] != 'X' && getqsl(lb[i-c[j]-1], i-c[j]-1, j-1) && !(c.size() == j+1 && getbc(i+1, s.size()-1))) dpl[i][j] = 1;
      |                                                                                                                    ~~~~~~~~~^~~~~~
paint.cpp:44:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if(i+c[c.size()-1] <= s.size() && getwc(i, i+c[c.size()-1]-1) == 0 && !getbc(i+c[c.size()-1], s.size()-1) && !(c.size() == 1 && getbc(0, i-1))) dpr[i][c.size()-1] = 1;
      |            ~~~~~~~~~~~~~~~~^~~~~~~~~~~
paint.cpp:46:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         qsr[i][c.size()-1] = dpr[i][c.size()-1] + (i == s.size()-1 ? 0 : qsr[i+1][c.size()-1]);
      |                                                    ~~^~~~~~~~~~~~~
paint.cpp:50:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if(i+c[j]+2 <= s.size() && getwc(i, i+c[j]-1) == 0 && s[i+c[j]] != 'X' && getqsr(i+c[j]+1, rb[i+c[j]+1], j+1) && !(!j && getbc(0, i-1))) dpr[i][j] = 1;
      |                ~~~~~~~~~^~~~~~~~~~~
paint.cpp:52:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             qsr[i][j] = dpr[i][j] + (i == s.size()-1 ? 0 : qsr[i+1][j]);
      |                                      ~~^~~~~~~~~~~~~
paint.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0;i+1<s.size();i++)
      |                 ~~~^~~~~~~~~
paint.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=1;i<s.size();i++)
      |                 ~^~~~~~~~~
paint.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0;i+2<s.size();i++) {
      |                 ~~~^~~~~~~~~
paint.cpp:62:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int j=0;j+1<c.size();j++) {
      |                     ~~~^~~~~~~~~
paint.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int j=0;j<c.size();j++) {
      |                 ~^~~~~~~~~
paint.cpp:68:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if(j == c.size()-1) {
      |            ~~^~~~~~~~~~~~~
paint.cpp:69:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for(int i=0;i<s.size();i++) {
      |                         ~^~~~~~~~~
paint.cpp:74:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for(int i=0;i+2<s.size();i++) {
      |                         ~~~^~~~~~~~~
paint.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0;i<s.size();i++) {
      |                 ~^~~~~~~~~
paint.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0;i<s.size();i++) {
      |                 ~^~~~~~~~~

• 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