Submission #966818

#	Time	Username	Problem	Language	Result	Execution time	Memory
966818		anango	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1644 ms	296388 KiB

paint

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

vector<int> prefX={0};
vector<int> pref_={0};
int n;
int getX(int l, int r) {
    //get X in the interval inclusive
    return prefX[min(r+1,n)] - prefX[l];
}
int get_(int l, int r) {
    //get _ in the interval inclusive
    return pref_[r+1] - pref_[l];
}
vector<vector<bool>> getdp(string s, vector<int> &prefX, vector<int> &pref_, vector<int> c) {
    int k=c.size();
    vector<vector<bool>> dp(n+2, vector<bool>(k+1));
    dp[0][0] = 1;
    //with the last segment covering i-2 (so can start at i) and having covered j segments already
    for (int j=0; j<=k; j++) {
        for (int i=0; i<n; i++) {
            if (!getX(i,i)) dp[i+1][j] = dp[i+1][j] | dp[i][j];
        }
        if (j==k) {
            break;
        }
        for (int i=0; i<n-c[j]+1; i++) {
            if (!get_(i, i+c[j]-1) && !getX(i+c[j], i+c[j])) dp[i+c[j]+1][j+1] = dp[i+c[j]+1][j+1] | dp[i][j];
        }
    }
    for (int i=0; i<n+2; i++) {
        for (int j=0; j<=k; j++) {
            //cout << dp[i][j] << " ";
        }
        //cout << endl;
    }
    return dp;

}
void update_pref(string s) {
    prefX = vector<int>(n+1,0);
    pref_ = vector<int>(n+1,0);
    for (int i=0; i<n; i++) {
        prefX[i+1] = prefX[i]+(s[i]=='X');
        pref_[i+1] = pref_[i]+(s[i]=='_');
    }
}

string solve_puzzle(string s, vector<int> c) {
    n=s.size();
    update_pref(s);
    vector<vector<bool>> forwarddp = getdp(s,prefX, pref_, c);
    //forwarddp[index][j] = is it possible to get next pos start at index, with j used to the left
    reverse(s.begin(), s.end());
    update_pref(s);
    reverse(c.begin(), c.end());
    //cout << endl;
    vector<vector<bool>> backwarddp = getdp(s,prefX, pref_, c);
    //backward[index][j] = is it possible to get next pos start at n-index-1, with j used to the right
    reverse(s.begin(), s.end());
    update_pref(s);
    reverse(c.begin(), c.end());
    vector<pair<int,int>> goodxint;
    int k=c.size();
    vector<int> answers(n,0); //0 = fail both, 1 = X, 2 = _, 3 = X or _
    for (int j=0; j<=k; j++) {
        for (int start=0; start<n; start++) {
            //consider putting a whitespace in start
            if (getX(start, start)==0 && forwarddp[start+1][j] && backwarddp[n-(start-1)-1][k-j]) {
                answers[start] |= 2;
            }
            if (!(start<n-c[j]+1) || j==k) {
                continue;
            }
            int end = start+c[j]-1;
            //cout << start << " " << end << " " << j << endl;
            //fw[start+1] and bw[end-1]
            if (get_(start,end)==0 && forwarddp[start][j] && backwarddp[n-(end)-1][k-j-1]) {
                goodxint.push_back({start,end}); //everything in these bounds inclusive is good
                ////cout << "adding" << " " << start << " " << end << endl;
            }

        }
    }
    //cout << "ANSWERS1 ";
    for (int i=0; i<n; i++) {
        //cout <<answers[i] << " ";
    }
    //cout << endl;
    vector<pair<int,int>> finalint;
    sort(goodxint.begin(), goodxint.end());
    for (int i=0; i<goodxint.size(); i++) {
        int fi,se;
        fi=goodxint[i].first;
        se=goodxint[i].second;
        if (!finalint.size()) {
            finalint.push_back(goodxint[i]);
        }
        else {
            if (fi>finalint.back().second) {
                finalint.push_back(goodxint[i]);
            }
            else if (se>finalint.back().second) {
                pair<int,int> last=finalint.back();
                finalint.pop_back();
                finalint.push_back({last.first,se});
            }
            
        }
    }
    for (int i=0; i<finalint.size(); i++) {
        for (int j=finalint[i].first; j<=finalint[i].second; j++) {
            answers[j] |= 1;
        }
    }
    //cout << "ANSWERS2 ";
    for (int i=0; i<n; i++) {
        //cout <<answers[i] << " ";
    }
    //cout << endl;
    string fans;
    for (int i=0; i<n; i++) {
        assert(answers[i]!=0);
        if (answers[i]==1) {
            fans.push_back('X');
        }
        else if (answers[i]==2) {
            fans.push_back('_');
        }
        else if (answers[i]==3) {
            fans.push_back('?');
        }
    }

    return fans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i=0; i<goodxint.size(); i++) {
      |                   ~^~~~~~~~~~~~~~~~
paint.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i=0; i<finalint.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