Submission #334461

#	Time	Username	Problem	Language	Result	Execution time	Memory
334461		Swan	Paint By Numbers (IOI16_paint)	C++14	100 / 100	633 ms	10268 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 3;
const int maxk = 101;

bitset<maxk> pref[maxn];
bitset<maxk> suf[maxn];
int prefSum[maxn];
int prefSumBlack[maxn];
int isWhiteGood[maxn];
string ans;
int n;
int k;

void addWhite(int l, int r){
    isWhiteGood[l]++;
    isWhiteGood[r + 1]--;
}

int getSum(int l, int r){
    int res = prefSum[r];
    if(l)res-=prefSum[l - 1];
    return res;
}

int getSumBlack(int l, int r){
    int res = prefSumBlack[r];
    if(l)res-=prefSumBlack[l - 1];
    return res;
}

bool canSuf(int sufNum, int need){
    if(sufNum == n){
        if(need == k)return 1;
        else return 0;
    }
    if(need == k){
        if(sufNum >= n)return 1;
        int sufSum = getSumBlack(sufNum, n - 1);
        if(sufSum)return 0;
        else return 1;
    }
    if(sufNum >= n)return 0;
    return suf[sufNum][need];
}

bool canPref(int prefNum, int need){
    if(prefNum == -1){
        if(need == 0)return 1;
        else return 0;
    }
    if(need == 0){
        if(prefNum <= -1)return 1;
        int prefSum = getSumBlack(0, prefNum);
        if(prefSum)return 0;
        else return 1;
    }
    if(prefNum < 0)return 0;
    return pref[prefNum][need - 1];
}

void solveBlack(string& s, string& ans){
    for(int i = 0; i < s.size();i++){
        if(s[i] != '.')continue;
        bool can = 0;
            for(int prefCnt = 0; prefCnt<= k;prefCnt++){
                int sufCnt = prefCnt;
                if(canPref(i - 1, prefCnt) && canSuf(i + 1, sufCnt)){
                    can = 1;
                }
            }
            if(!can){
                ans[i] = 'X';
            }
    }
}

bool putBlock(int l, int r, int j, string& s){
    if(l){
        if(s[l - 1] == 'X')return 0;
    }
    if(r != s.size() - 1){
        if(s[r + 1] == 'X')return 0;
    }
    //cout << "MDA " << l << ' ' << r << ' ' << j << ' ' << canPref(l - 2, j) << ' ' << canSuf(r + 2, j + 1) << endl;
    return ((canPref(l - 2, j) && canSuf(r + 2, j + 1)));
}

void solveWhite(string& s, vector<int>& c, string& ans){
    for(int j = 0; j < c.size();j++){
        for(int l = 0 ; l < s.size();l++){
            int r = l + c[j] - 1;
            if(r >= s.size())continue;
            if(getSum(l, r))continue;
            if(putBlock(l, r, j, s)){
                addWhite(l, r);
                //cout << "OPA " << l << ' ' << r << endl;
            }
        }
    }
    int nowSum = 0;
    for(int i = 0; i < n;i++){
        nowSum+=isWhiteGood[i];
        if(s[i] != '.')continue;
        //cout << i << ' ' << nowSum << endl;
        if(nowSum == 0){
            ans[i] = '_';
        }
    }
}

void calc_suf(vector<int>& c, string& s){
    for(int i = s.size() - 1; i >= 0;i--){
        for(int j = c.size() - 1; j >= 0;j--){
            if(s[i] != 'X' && i != s.size() - 1)suf[i][j] = suf[i + 1][j];
            int r = i + c[j] - 1;
            if(r >= s.size())continue;
            int sumOnSegm = getSum(i, r);
            //cout << "SUF " << i << ' ' << j << ' ' << sumOnSegm << endl;
            if(sumOnSegm)continue;
            //cout << i << ' ' << j << endl;
            if(j == c.size() - 1){
                if(r == s.size() - 1){
                    suf[i][j] = 1;
                }else{
                    if(getSumBlack(r + 1, s.size() - 1)!=0)continue;
                    else suf[i][j] = 1;
                }
            }else{
                if(s[r + 1] == 'X')continue;
                if(r + 2 < s.size()){
                    if(suf[r + 2][j + 1]){
                        suf[i][j] = 1;
                    }
                }

            }
        }
    }
}

void calc_pref(vector<int>& c, string& s){
    for(int i = 0; i < s.size();i++){
        for(int j = 0; j < c.size();j++){
            if(s[i] != 'X' && i)pref[i][j] = pref[i - 1][j];
            int l = i - c[j] + 1;
            if(l < 0)continue;
            int sumOnSegm = getSum(l, i);
            if(sumOnSegm)continue;
            if(j == 0){
                if(l == 0){
                    pref[i][j] = 1;
                }else{
                    if(prefSumBlack[l - 1] != 0)continue;
                    else pref[i][j] = 1;
                }
            }else{
                if(s[l - 1] == 'X')continue;
                if(l - 2 >= 0){
                    if(pref[l - 2][j - 1]){
                        pref[i][j] = 1;
                    }
                }
            }
        }
    }
}

string solve_puzzle(string s, vector<int> c) {
    n = s.size();
    k = c.size();
    for(int i = 0; i < s.size();i++){
        if(s[i] == '_'){
            prefSum[i]++;
        }
        if(s[i] == 'X'){
            prefSumBlack[i]++;
        }
        if(s[i] != '.'){
            ans+= s[i];
        }else{
            ans+='?';
        }
        if(i){
            prefSum[i] += prefSum[i - 1];
            prefSumBlack[i] += prefSumBlack[i - 1];
        }
    }
    calc_pref(c, s);
    calc_suf(c, s);
    solveBlack(s, ans);
    solveWhite(s, c, ans);
//    for(int i = 0; i < n;i++){
//        cout << i << endl;
//        for(int j = 0; j <= k;j++){
//            cout << suf[i][j] << ' ';
//        }
//        cout << endl;
//    }
    return ans;
}


/*
..._..X._...
1
3
*/

Compilation message (stderr)

paint.cpp: In function 'void solveBlack(std::string&, std::string&)':
paint.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0; i < s.size();i++){
      |                    ~~^~~~~~~~~~
paint.cpp: In function 'bool putBlock(int, int, int, std::string&)':
paint.cpp:86:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     if(r != s.size() - 1){
      |        ~~^~~~~~~~~~~~~~~
paint.cpp: In function 'void solveWhite(std::string&, std::vector<int>&, std::string&)':
paint.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int j = 0; j < c.size();j++){
      |                    ~~^~~~~~~~~~
paint.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int l = 0 ; l < s.size();l++){
      |                         ~~^~~~~~~~~~
paint.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             if(r >= s.size())continue;
      |                ~~^~~~~~~~~~~
paint.cpp: In function 'void calc_suf(std::vector<int>&, std::string&)':
paint.cpp:119:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             if(s[i] != 'X' && i != s.size() - 1)suf[i][j] = suf[i + 1][j];
      |                               ~~^~~~~~~~~~~~~~~
paint.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             if(r >= s.size())continue;
      |                ~~^~~~~~~~~~~
paint.cpp:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             if(j == c.size() - 1){
      |                ~~^~~~~~~~~~~~~~~
paint.cpp:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |                 if(r == s.size() - 1){
      |                    ~~^~~~~~~~~~~~~~~
paint.cpp:135:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |                 if(r + 2 < s.size()){
      |                    ~~~~~~^~~~~~~~~~
paint.cpp: In function 'void calc_pref(std::vector<int>&, std::string&)':
paint.cpp:147:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for(int i = 0; i < s.size();i++){
      |                    ~~^~~~~~~~~~
paint.cpp:148:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for(int j = 0; j < c.size();j++){
      |                        ~~^~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:176:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |     for(int i = 0; i < s.size();i++){
      |                    ~~^~~~~~~~~~

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