Submission #392112

#	Time	Username	Problem	Language	Result	Execution time	Memory
392112		AugustinasJucas	Paint By Numbers (IOI16_paint)	C++14	80 / 100	8 ms	10732 KiB

paint

#include <bits/stdc++.h>
using namespace std;
const int dydis = 1e2 + 10;
int dp[dydis][dydis][dydis][2]; // jei esu i-ajame characteryje, j-ojoje grupeje, jau su manimi is viso yra h bloku, o as esu l characteris, tai ar galima taip padaryt?
string S;
vector<int> mas;
int hsh(char a){
    if(a == '_') return 0;
    if(a == 'X') return 1;
    return 2;
}
int galiButi[dydis][2] = {0};
bool galima(int i1, int i2, int sitasBlokasJau, int asEsu){
//    cout << "dp[" << i1 << "][" << i2  << "][" << sitasBlokasJau << "][" << asEsu << "] = ?\n";
    

    if(i1 == S.size()){
        if(i2 == mas.size() && sitasBlokasJau == 0) return true;
        return false;
    } 
    if(sitasBlokasJau == 1 && i2 == mas.size()) return false;
    if(S[i1] != '.'){
        if(hsh(S[i1]) != asEsu) return false;
    }
    if(dp[i1][i2][sitasBlokasJau][asEsu] != -1) return dp[i1][i2][sitasBlokasJau][asEsu];
    // dabar kazka desiu i kita!
    bool ret = 0;
    if(asEsu == hsh('_')){ // jei as esu _, tai toliau galiu testi save, arba pradeti nauja etapa
        bool p1 = 0, p2 = 0;
        p1 = galima(i1+1, i2, 1, hsh('X'));
        p2 = galima(i1+1, i2, 0, hsh('_'));
        ret = p1 | p2;
    }else{ // jei as esu X, tai privalau arba testi, arba privalau uzbaigti etapa
        
        if(sitasBlokasJau == mas[i2]) { // privalau uzbaigti
            ret = galima(i1+1, i2+1, 0, hsh('_'));
        }else{ // privalau testi
            ret = galima(i1+1, i2, sitasBlokasJau+1, hsh('X'));
        }
    }
    if(ret){
        galiButi[i1][asEsu] = 1;
    }
//    cout << "dp[" << i1 << "][" << i2  << "][" << sitasBlokasJau << "][" << asEsu << "] = " << ret << endl;
    return dp[i1][i2][sitasBlokasJau][asEsu] = ret;
    // esu jau nustates S[i1]
}
string solve_puzzle(string s, vector<int> c) {
    for(int i = 0; i < dydis; i++){
        for(int j = 0; j < dydis; j++){
            for(int h = 0; h < dydis; h++){
                for(int l = 0; l < 2; l++){
                    dp[i][j][h][l] = -1;
                }
            }
        }
    }
    int k = c.size();
    S = s;
    mas = c;
    galima(0, 0, 0, hsh('_'));
    galima(0, 0, 1, hsh('X'));
    string ret  = "";
    for(int i = 0; i < s.size(); i++){
        if(galiButi[i][hsh('_')] == 1 && galiButi[i][hsh('X')]){
            ret.push_back('?');
        }else if(galiButi[i][hsh('X')] == 1){
            ret.push_back('X');
        }else if(galiButi[i][hsh('_')] == 1){
            ret.push_back('_');
        }else{
            ret.push_back('!');
        }
    }
    return ret;
}

Compilation message (stderr)

paint.cpp: In function 'bool galima(int, int, int, int)':
paint.cpp:17:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     if(i1 == S.size()){
      |        ~~~^~~~~~~~~~~
paint.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if(i2 == mas.size() && sitasBlokasJau == 0) return true;
      |            ~~~^~~~~~~~~~~~~
paint.cpp:21:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if(sitasBlokasJau == 1 && i2 == mas.size()) return false;
      |                               ~~~^~~~~~~~~~~~~
paint.cpp:45:46: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   45 |     return dp[i1][i2][sitasBlokasJau][asEsu] = ret;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
paint.cpp:58:9: warning: unused variable 'k' [-Wunused-variable]
   58 |     int k = c.size();
      |         ^

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