Submission #968707

#	Time	Username	Problem	Language	Result	Execution time	Memory
968707		MarwenElarbi	Paint By Numbers (IOI16_paint)	C++17	100 / 100	335 ms	259460 KiB

paint

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

std::string solve_puzzle(std::string S, std::vector<int> C) {
    int n=S.size();
    vector<int> black;
    vector<int> white;
    for (int i = 0; i < n; ++i)
    {
        if(S[i]=='X') black.push_back(i);
        if(S[i]=='_') white.push_back(i);
    }
    n+=2;
    int k=C.size();
    for (int i = 0; i < black.size(); ++i) black[i]++;
    for (int i = 0; i < white.size(); ++i) white[i]++;
    vector<int> preB;
    vector<int> preW;
    vector<vector<vector<int>>> dp (2,vector<vector<int>>(n,vector<int> (k+1,0)));
    for (int it = 0; it < 3; ++it)
    {
        preB.assign(n,0);
        preW.assign(n,0);
        for(auto u:black) preB[u]++;
        for(auto u:white) preW[u]++;
        for (int i = 1; i < n; ++i)
        {
            preB[i]+=preB[i-1];
            preW[i]+=preW[i-1];
        }
        if(it==2) break;
        dp[it][0][0]=1;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j <= k; ++j)
            {
                dp[it][i][j]|= dp[it][i-1][j] && (preB[i]-preB[i-1] == 0);
                dp[it][i][j]|= j > 0 && i > C[j-1] && (preW[i-1]-preW[i-C[j-1]-1] == 0) && (preB[i]-preB[i-1] == 0) && (dp[it][i-C[j-1]-1][j-1]);
                //cout <<i<<" "<<j<<" "<<dp[it][i][j]<<endl;
            }
        }//cout <<"nabba"<<endl;
        reverse(black.begin(),black.end());
        reverse(white.begin(),white.end());
        reverse(C.begin(),C.end());
        for (int i = 0; i < (int)black.size(); ++i) black[i]=n-black[i]-1;
        for (int i = 0; i < (int)white.size(); ++i) white[i]=n-white[i]-1;
    }//cout <<"nabba"<<endl;
    vector<int> ans(n,0);
    reverse(dp[1].begin(),dp[1].end());
    for (int i = 1; i < n-1; ++i)
    {
        for (int j = 0; j <= k; ++j)
        {
            if(dp[0][i][j]&&dp[1][i][k-j]){
                //cout <<i-1<<endl;
                ans[i-1]|=1;
            }
        }
    }
    vector<int> cur(n,0);
    for (int i = 1; i < n; ++i)
    {
        //cout <<i<<endl;
        for (int j = 0; j <= k; ++j)
        {
            //cout <<j<<" ";
            if(j > 0 && i > C[j-1] && preW[i-1]-preW[i-C[j-1]-1] == 0 && preB[i]-preB[i-1] == 0 && dp[0][i-C[j-1]-1][j-1] && dp[1][i][k-j]){
                cur[i-C[j-1]]++;
                cur[i]--;
            }
        }//cout <<endl;
    }
    for (int i = 1; i < n; ++i)
    {
        cur[i]+=cur[i-1];
        //cout <<cur[i]<<" ";
        if(cur[i]>0){
            ans[i-1]|=2;
            //cout <<i-1<<" "<<ans[i-1]<<endl;
        }//cout <<endl;
    }
    string res="";
    for (int i = 0; i < n-2; ++i)
    {

        if(ans[i]==1) res.push_back('_');
        else if(ans[i]==2) res.push_back('X');
        else res.push_back('?');
    }
    return res;
}


/*const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];

int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    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;
}*/

Compilation message (stderr)

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