Submission #116441

#	Time	Username	Problem	Language	Result	Execution time	Memory
116441		Meloric	Paint By Numbers (IOI16_paint)	C++14	59 / 100	3 ms	640 KiB

paint

#include "paint.h"
#include <iostream>
#include <cstdlib>
#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;

vector<vector<vector<int>>> dp;
vector<pii> ans;
vector<vector<int>> vis;
void color(int n, int k, vector<int>&c){
    if(n < 0)return;
    if(vis[n][k])return;
    vis[n][k] = 1;
    if(dp[n][k][0]){
        ans[n].X = 1;
        color(n-1, k, c);
    }
    if(dp[n][k][1]){
        color(n-c[k-1]-1, k-1, c);
        ans[n-c[k-1]].X=1;
        ans[n-c[k-1]].Y++;
        ans[n].Y--;
    }
}
string solve_puzzle(string s, vector<int> c) {
    vector<int> bla, whi;
    int n = s.size();
    bla.pb(0); whi.pb(0);
    ans.assign(n+1, {0, 0});
    for(auto i : s){
        if(i == '_'){
            whi.pb(whi.back()+1);
            continue;
        }
        if(i == 'X'){
            bla.pb(bla.back()+1);
            continue;
        }
        bla.pb(bla.back());
        whi.pb(whi.back());
    }
    int k = c.size();

    dp.assign(n+1, vector<vector<int>>(k+1, vector<int>(2)));
    vis.assign(n+1, vector<int>(k+1));
    dp[0][0][0] = 1;
    for(int i = 0; i< s.size(); i++){
        if(s[i] == 'X')break;
        dp[i+1][0][0] = 1;
    }
    for(int i = 0; i < s.size(); i++){
        for(int j = 0; j < k; j++){
            if(s[i] != 'X'){
                dp[i+1][j+1][0] = max(dp[i][j+1][0], dp[i][j+1][1]);
            }
            if(s[i] != '_'){
                if(i+1-c[j]>=0){
                    if(whi[i+1]- whi[i+1-c[j]] == 0){
                        dp[i+1][j+1][1] = dp[i+1-c[j]][j][0];
                    }
                }
            }
        }
    }
    /*
    for(auto i : dp){
        for(auto j : i){
            cout << j[0]<<' '<<j[1]<<'|';
        }
        cout << '\n';
    }*/
    color(n, k, c);
    string ret;
    for(int i = 1; i < ans.size(); i++){
        if(ans[i].X > 0 && ans[i-1].Y>0){
            ret.pb('?');
            ans[i].Y+=ans[i-1].Y;
            continue;
        }
        if(ans[i].X > 0){
            ret.pb('_');
            ans[i].Y+=ans[i-1].Y;
            continue;
        }
        ret.pb('X');
        ans[i].Y+=ans[i-1].Y;
    }
    //return "?????????????";
    return ret;
    //return "";
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:51:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i< s.size(); i++){
                    ~^~~~~~~~~~
paint.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s.size(); i++){
                    ~~^~~~~~~~~~
paint.cpp:78:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < ans.size(); i++){
                    ~~^~~~~~~~~~~~

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