Submission #392177

#	Time	Username	Problem	Language	Result	Execution time	Memory
392177		AugustinasJucas	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1224 ms	62672 KiB

paint

#include <bits/stdc++.h>
using namespace std;
const int dydis1 = 2e5 + 10;
const int dydis2 = 1e2 + 10;
short dp[dydis1][dydis2]; // 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[dydis1][2] = {0};
int pref[dydis1] = {0};
int kiek_(int l, int r){
    if(l >= S.size()) return 0;
    r = min(r, (int) S.size()-1);

    int R = pref[r];
    int L = (l == 0 ? 0 : pref[l-1]);
    return R - L;
}
void nustatyk(int l, int r, int kas){
    for(int i = l; i <= r; i++){
        galiButi[i][kas] = 1;
    }
}
bool galima(int i1, int i2){ // as esu i1, dabartine grupe bus pildoma i2, ir pries mane yra padetas _
//    if(mas[i1] == 'X') return false;    
    if(i1 >= S.size()){
        return i2 == mas.size();
    }
    if(dp[i1][i2] != -1) return dp[i1][i2];
    // desiu X
    int ret = 0;
    if(i2 < mas.size() && i1 + mas[i2]-1 < S.size()){ // jei galiu deti X-u eile ir jei X-ai isvis telpa
        int kek = kiek_ (i1, i1+mas[i2]-1);
        if(kek == 0 && (i1 + mas[i2] == S.size() || S[i1+mas[i2]] != 'X')){ // jei nera trukdziu nei tarpe nei sone
            
            int p1 = galima(i1 + mas[i2]+1, i2+1);
            if(p1){ 
                ret = 1;
                nustatyk(i1, i1+mas[i2]-1, hsh('X')); // nustatyk ,kad gali X-a paimti
                nustatyk(i1+mas[i2], i1 + mas[i2], hsh('_'));
            }
        }
    } 
    if(S[i1] != 'X'){ 
        if(galima(i1+1, i2)){
            ret = 1;
            nustatyk(i1, i1, hsh('_'));
        }
    }
//    cout << "DP[" << i1 << "][" << i2 << "] = " << ret << endl;
    return dp[i1][i2] = ret;
    // desiu _    

}
string solve_puzzle(string s, vector<int> c) {
    for(int i = 0; i < dydis1; i++){
        for(int j = 0; j < dydis2; j++){
            dp[i][j] = -1;
        }
    }
    int k = c.size();
    S = s;
    mas = c;
    for(int i = 0; i < s.size(); i++){
        pref[i] = (i == 0 ? 0 : pref[i-1]) + (s[i] == '_');
    }
    if(c[0] == 'X'){
        nustatyk(0, mas[0]-1, hsh('X'));
        nustatyk(mas[0], mas[0], hsh('_'));
        galima(mas[0]+1, 1);
    }else{
        galima(0, 0);
    }
    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 'int kiek_(int, int)':
paint.cpp:16:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     if(l >= S.size()) return 0;
      |        ~~^~~~~~~~~~~
paint.cpp: In function 'bool galima(int, int)':
paint.cpp:30:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     if(i1 >= S.size()){
      |        ~~~^~~~~~~~~~~
paint.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         return i2 == mas.size();
      |                ~~~^~~~~~~~~~~~~
paint.cpp:36:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if(i2 < mas.size() && i1 + mas[i2]-1 < S.size()){ // jei galiu deti X-u eile ir jei X-ai isvis telpa
      |        ~~~^~~~~~~~~~~~
paint.cpp:36:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if(i2 < mas.size() && i1 + mas[i2]-1 < S.size()){ // jei galiu deti X-u eile ir jei X-ai isvis telpa
      |                           ~~~~~~~~~~~~~~~^~~~~~~~~~
paint.cpp:38:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if(kek == 0 && (i1 + mas[i2] == S.size() || S[i1+mas[i2]] != 'X')){ // jei nera trukdziu nei tarpe nei sone
      |                         ~~~~~~~~~~~~~^~~~~~~~~~~
paint.cpp:55:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   55 |     return dp[i1][i2] = ret;
      |            ~~~~~~~~~~~^~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
paint.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
paint.cpp:65:9: warning: unused variable 'k' [-Wunused-variable]
   65 |     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: 10 / 10
• Subtask 7: 10 / 10