Submission #65317

#	Time	Username	Problem	Language	Result	Execution time	Memory
65317		zubec	Paint By Numbers (IOI16_paint)	C++14	100 / 100	752 ms	403536 KiB

paint

#include "paint.h"

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

int dp[110][200100], n, k, pref[200100], ptrL[110], ptrR[110], pref2[200100];
int good[110][200100];
int sum[110][200100];
int can1[200100], can2[200100];

pair<int, int> prs[110][200100];

vector <int> vec[110];

std::string solve_puzzle(std::string s, std::vector<int> c) {

    s += '_';
    s += 'X';
    c.push_back(1);
    n = s.size();
    s = '.' + s;
    k = c.size();
    for (int i = 1; i <= n; i++){
        pref[i] = pref[i-1];
        pref2[i] = pref2[i-1];
        if (s[i] == '_')
            ++pref[i];
        if (s[i] == 'X')
            ++pref2[i];
    }
    bool bb = 0;
    for (int i = 0; i <= n; i++){
        if (s[i] == 'X')
            bb = 1;
        if (bb == 1)
            break;
        vec[0].push_back(i);
    }
    for (int j = 1; j <= k; j++){
        int sz = c[j-1];
        for (int i = sz; i <= n; i++){
            if (j == k && i != n)
                continue;
            if (pref[i]-pref[i-sz] > 0)
                continue;
            while(ptrR[j-1] + 1 < vec[j-1].size() && vec[j-1][ptrR[j-1]+1] < i - sz + (j == 1))
                ++ptrR[j-1];
            while(ptrL[j-1] < vec[j-1].size() && pref2[i-sz]-pref2[max(0, vec[j-1][ptrL[j-1]])] > 0)
                ++ptrL[j-1];
            //cout << j << ' ' << i << ' ' << ptrL[j-1] << ' ' << ptrR[j-1] << ' ' << vec[j-1][ptrL[j-1]] << endl;
            if (ptrR[j-1] < vec[j-1].size() && ptrL[j-1] <= ptrR[j-1] && vec[j-1][ptrL[j-1]] < i - sz + (j == 1)){
                dp[j][i] = 1;
                vec[j].push_back(i);
                prs[j][vec[j].size()-1] = {ptrL[j-1], ptrR[j-1]};
            }
        }
    }
    sum[k][0] = 1;
    for (int j = k; j >= 1; j--){
        int curSum = 0;
        for (int i = 0; i < vec[j].size(); i++){
            //break;
            curSum += sum[j][i];
            if (curSum > 0){
                int l = prs[j][i].first, r = prs[j][i].second;
                //cout << j << ' ' << l << ' ' << r << ' ' << vec[j][i] << ' ' << vec[j][i]-c[j-1]+1 << ' ' << vec[j][i] << endl;
                ++sum[j-1][l];
                --sum[j-1][r+1];
                ++can1[vec[j][i]-c[j-1]+1];
                --can1[vec[j][i]+1];
                int sz2;
                if (j > 1)
                    sz2 = c[j-2]; else
                    sz2 = 1;
                /*int lSpace = vec[j-1][l]-sz2+1, rSpace = vec[j-1][r]-sz2+1;
                cout << lSpace << ' ' << rSpace << ' ';
                ++can2[lSpace];
                --can2[rSpace];*/
                int lSpace = vec[j-1][l]+1, rSpace = vec[j][i]-c[j-1]+1;
                //cout << lSpace << ' ' << rSpace << endl;
                ++can2[lSpace];
                --can2[rSpace];
            }
        }
    }
    int sum1 = 0, sum2 = 0;
    string anss;
    for (int i = 1; i <= n-2; i++){
        sum1 += can1[i];
        sum2 += can2[i];
        //cout << i << ' ' << "kek " << sum1 << ' ' << sum2 << ' ' << endl;
        if (s[i] != '.'){
            anss += s[i];
            continue;
        }
        if (sum1 > 0 && sum2 > 0)
            anss += '?'; else
        if (sum1 > 0)
            anss += 'X'; else
            anss += '_';
    }

    /*for (int i = 1; i <= k; i++){
        for (int j = 0; j < vec[i].size(); j++)
            cout << vec[i][j] << ' ';
        cout << endl;
    }*/
    return anss;
}

/**


...X....X.
2
3 4

*/

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:46:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(ptrR[j-1] + 1 < vec[j-1].size() && vec[j-1][ptrR[j-1]+1] < i - sz + (j == 1))
                   ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
paint.cpp:48:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(ptrL[j-1] < vec[j-1].size() && pref2[i-sz]-pref2[max(0, vec[j-1][ptrL[j-1]])] > 0)
                   ~~~~~~~~~~^~~~~~~~~~~~~~~~~
paint.cpp:51:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (ptrR[j-1] < vec[j-1].size() && ptrL[j-1] <= ptrR[j-1] && vec[j-1][ptrL[j-1]] < i - sz + (j == 1)){
                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~
paint.cpp:61:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < vec[j].size(); i++){
                         ~~^~~~~~~~~~~~~~~
paint.cpp:71:21: warning: variable 'sz2' set but not used [-Wunused-but-set-variable]
                 int sz2;
                     ^~~

• 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