Submission #1197486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197486		joker	Paint By Numbers (IOI16_paint)	C++20	59 / 100	1 ms	328 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;


int lwb (vector<int> &whts,int i) {
    int l = 0;
    int r = whts.size()-1;
    int ans = 0;
    while (l <= r) {
        int mid = l + (r-l)/2;
        if (whts[mid] == i) {
            return mid;
        } else if (whts[mid] > i) {
            r = mid - 1;
        } else {
            ans = mid;
            l = mid + 1;
        }
    }
    return ans;
}

string solve_puzzle(string s, vector<int> c) {
    string t;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        t += '_';
        // if (s[i] == '_') t[i] = s[i];
    }
    int k = c.size();
    vector<int> whts = {-1};
    for (int i = 0; i < n; i++) {
        if (s[i] == '_') whts.push_back(i);
    }
    whts.push_back(n);

    vector<int> prf(k);
    vector<int> suff(k);
    int iprf = 0;
    int lk = 0;
    while (iprf < n && lk < k) {
        int lb = lower_bound(whts.begin(),whts.end(), iprf) - whts.begin();
        if (whts[lb]-iprf < c[lk]) {
            iprf = whts[lb]+1;
            continue;
        }
        prf[lk] = iprf;
        iprf += c[lk]+1;
        lk++;
    }

    lk = k-1;
    iprf = n-1;
    while (lk >= 0 && iprf >= 0) {
        int lb = lwb(whts, iprf);
        if (iprf-whts[lb] < c[lk]) {
            iprf = whts[lb]-1;
            continue;
        }
        suff[lk] = iprf;
        iprf -= c[lk]+1;
        lk--;
    }

    for (int i = 0; i < k; i++) {
        pair<int,int> intrvl = make_pair(prf[i],suff[i]);
        vector<pair<int,int>> sgmnt;
        int str = intrvl.first;

        for (int j = intrvl.first; j <= intrvl.second; j++) {
            if (s[j] == '_') {
                if (j-str >= c[i]) sgmnt.push_back({str, j - 1});
                str = j + 1;
            }
        }
        if (intrvl.second-str+1 >= c[i]) sgmnt.push_back({str,intrvl.second});
        for (auto pr:sgmnt) {
            if (sgmnt.size() > 1) {
                for (int j = pr.first; j <= pr.second; j++) {
                    t[j] = '?';
                }
            } else {
                int extr = pr.second-pr.first+1-c[i];
                for (int j = pr.first; j <= pr.second; j++) {
                    if ((j-pr.first+1) <= extr || (pr.second-j+1) <= extr) t[j] = '?';
                    else t[j] = 'X';
                }
            }
        }
    }

    // for (int i = 0; i < n; i++) {
    //     if (t[i] != '?' && t[i] != '_') t[i] = 'X';
    // }
    return t;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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