Submission #73612

#	Time	Username	Problem	Language	Result	Execution time	Memory
73612		dmfr	Paint By Numbers (IOI16_paint)	C++11	32 / 100	6 ms	648 KiB

paint

///http://ioi2016.ru/uploads/file_store/attached_file/26/paint.pdf
///https://oj.uz/problem/view/IOI16_paint
#include "paint.h"

#include <numeric>

#include <iostream>

using namespace std;

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

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

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

........
2
3 4
=>XXX_XXXX
*/

    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;
            }
        }
    }

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

    if(NoInfo == N){
//        if(N == sum(0,K-1)+(K-1)){
//            string ret(s);
//            int index = 0;
//            for(int i = 0; i < K; ++i){
//                for(int j = 0; j < c[i]; ++j, ++index){
//                    ret[index] = 'X';
//                }
//                if(i != K-1)
//                    ret[index++] = '_';
//            }
//            return ret;
//        }else{
            string ret(N, '0');
            for(int hint = 0; hint < K; ++hint){

//                cout << ret << endl;

                int Left_left = sum(0,hint-1) + hint;
                int Right_right = N-1 - 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';
//                    switch(ret[i]){
//                        case '0': ret[i] = 'X';
//                        case '_': ret[i] = '?';
//                        default: break;
//                    }
            }

            for(auto& i:ret)
                if(i == '0')
                    i = '_';

//            cout << endl;
            return ret;

//        }
    }



    return "";
}

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