Submission #117103

#	Time	Username	Problem	Language	Result	Execution time	Memory
117103		Meloric	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1046 ms	105736 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<int>> mem;
vector<int> whi;
vector<pii> ans;
int n, k;
int dp(int i, int j, string &s, vector<int>& c){
    if(i >= n && j == k)return 1;
    if(i >= n)return 0;
    if(j==k && s[i] == 'X')return 0;
    if(mem[i][j]!=-1)return mem[i][j];
    int val = 0;
    if(s[i]!='X'){
        if(dp(i+1, j, s, c)){
            ans[i].X = 1;
            val = 1;
            //cout << i << ' '<<j <<'i'<<'\n';
        }
    }
    if(j != k && i+c[j] < whi.size() && whi[i+c[j]]-whi[i] == 0){
        if(i+c[j] == s.size() || s[i+c[j]] != 'X'){
            if(dp(i+c[j]+1, j+1, s, c)){
                ans[i+c[j]].X = 1;
                ans[i].Y++;
                ans[i+c[j]].Y--;
                val = 1;
            }
        }
    }
    mem[i][j] = val;
    return val;
}
string solve_puzzle(string s, vector<int> c) {
    n = s.size(); k = c.size();
    mem.assign(n+1, vector<int>(k+1, -1));
    ans.assign(n+1, {0, 0});
    whi.pb(0);
    for(auto i : s){
        if(i == '_'){
            whi.pb(whi.back()+1);
        }else{
            whi.pb(whi.back());
        }
    }
    dp(0, 0, s, c);
    for(int i = 1; i < ans.size(); i++){
        ans[i].Y+=ans[i-1].Y;
    }
    string ret;
    for(int i = 0; i < ans.size()-1; i++){
        if(ans[i].X == 1 && ans[i].Y>0){
            ret.pb('?');
            continue;
        }
        if(ans[i].X == 1){
            ret.pb('_');
            continue;
        }
        if(ans[i].Y>0){
            ret.pb('X');
            continue;
        }
    }
    /*
    for(auto i : mem){
        for(auto j : i){
            cout << j <<' ';
        }
        cout << '\n';
    }
    for(auto i : ans){
        cout << i.X << ' ';
    }*/
    //cout << ret;
    return ret;
}

Compilation message (stderr)

paint.cpp: In function 'int dp(int, int, std::__cxx11::string&, std::vector<int>&)':
paint.cpp:27:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(j != k && i+c[j] < whi.size() && whi[i+c[j]]-whi[i] == 0){
                  ~~~~~~~^~~~~~~~~~~~
paint.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i+c[j] == s.size() || s[i+c[j]] != 'X'){
            ~~~~~~~^~~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < ans.size(); i++){
                    ~~^~~~~~~~~~~~
paint.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size()-1; 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