Submission #107141

#	Time	Username	Problem	Language	Result	Execution time	Memory
107141		tictaccat	Paint By Numbers (IOI16_paint)	C++14	59 / 100	3 ms	512 KiB

paint

    #include "paint.h"
    #include <cstdlib>
    #include <bits/stdc++.h>
     
    using namespace std;
     
    std::string solve_puzzle(std::string s, std::vector<int> c) {
     
        int n = s.size(); int k = c.size();
     
        vector<int> right(k+1,0), left(k+1,0);

        int lenR = 0, lenL = 0;

        for (int i = 1; i <= k; i++) {
            if (i != 1) {lenR++; lenL++;}
            while (count(s.begin()+lenR,s.begin()+lenR+c[i-1],'_') > 0) lenR++;
            while (count(s.begin()+n-(lenL+c[k-i]),s.begin()+n-lenL,'_') > 0) lenL++;
            lenR += c[i-1]; lenL += c[k-i];
            right[i] = lenR; left[i] = lenL;
            //cout << i << " " << right[i] << " " << left[i] << "\n";
        }
        
        vector<bool> white(n,false), black(n,false);
     
        for (int pos = 0; pos < n; pos++) {
            assert(s[pos] != 'X');
            for (int i = 0; i <= k; i++) {
                //if (pos == n-1) cout << shortest[pos-j] << "\n";
                if (right[i] <= pos && left[k-i] <= n-1-pos) {
                //    cout << pos << " " << right[i] << " " << left[k-i] << "\n";
                    white[pos] = true;
                }
                if (i == k) continue;
                for (int shift = 0; shift < c[i]; shift++) {
                    if (count(s.begin()+pos-shift,s.begin()+pos-shift+c[i],'_') == 0 && (i == 0 || right[i] <= pos-shift-1) && (i == k-1 || left[k-1-i] <= n-(pos-shift+c[i]+1)) && (pos-shift >= 0) && (pos-shift+c[i]-1 < n)) {
                        assert(s[pos] != '_');
                     //   cout << pos << " " << i << " " << shift << "\n";
                        black[pos] = true;
                    }
                }
            }
            
        }
     
        string ans = s;
     
        for (int pos = 0; pos < n; pos++) {
            assert(white[pos] || black[pos]);
            if (white[pos] && black[pos]) ans[pos] = '?';
            else if (white[pos]) ans[pos] = '_';
            else if (black[pos]) ans[pos] = 'X';
        }
     
        return ans;
    }

• 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