Submission #73692

#	Time	Username	Problem	Language	Result	Execution time	Memory
73692		dmfr	Paint By Numbers (IOI16_paint)	C++11	59 / 100	9 ms	876 KiB

paint

#include "paint.h"

#include <numeric>

#include <deque>
#include <map>

#include <iostream>

using namespace std;

const string str_INVALID = "INVALID";

string add_strings(string s1, const string& s2){
    const int& N = s1.size();
    for(int i = 0; i < N; ++i){
              char& c1 = s1[i];
        const char& c2 = s2[i];
        if(c1 != c2){
            if(c1 == '?' || c2 == '?') c1 = '?';
            if(c1 == '0') c1 = c2;
            if((c1 == 'X' && c2 == '_')||
               (c1 == '_' && c2 == 'X')) c1 = '?';
        }
    }
    return s1;
}

int sum(const vector<int>& prefix_sum, const int& l, const int& r){
    if(r < l ) return 0;
    if(l == 0) return prefix_sum[r];
               return prefix_sum[r] - prefix_sum[l-1];
}

string solve_AllClear(const int& N, const deque<int>& c){
    const int& K = c.size();

    vector<int> prefix_sum = vector<int>(K);
    partial_sum(c.begin(), c.end(), prefix_sum.begin());

    if(K != 0 && prefix_sum.back() + (K-1) > N) return str_INVALID;

    string ret(N, '0');
    for(int hint = 0; hint < K; ++hint){
        int Left_left = sum(prefix_sum,0,hint-1) + hint;
        int Right_right = N-1 - sum(prefix_sum,hint+1,K-1) - (K-hint-1);
        int Right_left = Right_right - c[hint] + 1;
        int Left_right = Left_left + c[hint] - 1;
        for(int i = Left_left   ; i <  Right_left ; ++i)                   ret[i] = '?';
        for(int i = Left_right+1; i <= Right_right; ++i)                   ret[i] = '?';
        for(int i = Right_left  ; i <= Left_right ; ++i) if(ret[i] == '0') ret[i] = 'X';
    }
    for(auto& i:ret) if(i == '0') i = '_';
    return ret;
}

map<pair<string,deque<int>>, string> AMap;

string solvePart(const string& s, const deque<int>& c){
    const int& K = c.size();
    const int& N = s.size();

//    cout << "s:" << s << endl;

    string::size_type i = s.find('_');
    if(i == string::npos){
        string ret = solve_AllClear(s.size(), c);
        return ret;
    }else{
        auto it = AMap.find(pair<string,deque<int>>(s, c));
        if(it != AMap.end())
            return it->second;

        string::size_type j = i;
        while(s[j] == '_') ++j;
        const int& N1 = i;
        string s2(s, j, string::npos);
//        cout << "s2:" << s2 << endl;
        deque<int> c1;
        deque<int> c2(c);
        string ret1(i, '0');
        string ret_(j-i,'_');
        string ret2(N-j, '0');
        string ret(N, '0');
        string newret;
        for(int i = 0; i <= K; ++i){
            ret1 = solve_AllClear(N1, c1);
//            cout << "ret1:" << ret1 << endl;
            ret2 = solvePart(s2, c2);
//            cout << "ret2:" << ret2 << endl;
            if(ret1 != str_INVALID && ret2 != str_INVALID){
                newret = ret1+ret_+ret2;
                ret = add_strings(ret, newret);
//                cout << "ret:" << ret << endl;
            }
            if(i != K){
                c1.push_back(c[i]);
                c2.pop_front();
            }
        }
        if(ret == string(N, '0')) ret = str_INVALID;
        AMap[pair<string,deque<int>>(s, c)] = ret;
        return ret;
//        ret1 = solve_AllClear(s1);
    }
}

string solve_puzzle(string s, vector<int> c){

/*
..........
2
3 4
=>??X???XX??

........
2
3 4
=>XXX_XXXX

..._._....
1
3
=>???___????

...................._.._..........__....................
6
5 5 5 5 5 5

...................._....................
5
5 5 5 5 5

............_............
5
3 3 3 3 3


_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._.
4
1 1 1 1
=>_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?
*/

    const int& N = s.size();
    const int& K = c.size();

    int Black = 0, White = 0, NoInfo = 0;{
        for(const auto& ch:s){
            switch(ch){
                case 'X': ++ Black; break;
                case '_': ++ White; break;
                case '.': ++NoInfo; break;
                default :           break;
            }
        }
    }

    deque<int> cDqe(c.begin(),c.end());
//    if(NoInfo == N){
//        string ret = solve_AllClear(s.size(), cDqe);
//        return ret;
//    }else
    if(Black == 0){
        string ret = solvePart(s, cDqe);
        return ret;
    }



    return "";
}

Compilation message (stderr)

paint.cpp: In function 'int sum(const std::vector<int>&, const int&, const int&)':
paint.cpp:31:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(l == 0) return prefix_sum[r];
     ^~
paint.cpp:32:16: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
                return prefix_sum[r] - prefix_sum[l-1];
                ^~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:145:16: warning: unused variable 'N' [-Wunused-variable]
     const int& N = s.size();
                ^
paint.cpp:146:16: warning: unused variable 'K' [-Wunused-variable]
     const int& K = c.size();
                ^

• 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