제출 #427969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427969		Mazaalai	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	352 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
string solve_puzzle(string s, vector<int> c1) {
    int n = s.size(), k = c1.size();
    vector <int> c(k+5, 0);
    for (int i = 1; i <= k; i++) c[i] = c1[i-1];
    string ans = "";
    for (int i = 0; i < n+2; i++) {
        ans += '?';
    }
    for (int i = 1; i <= n; i++) {
        if (s[i-1] != '.') ans[i] = s[i-1];
    }
    vector <int> pre(k+5, 1), suf(k + 5, n);
    vector <int> white(1, 0), black;
    for (int i = 0; i < n; i++) {
        if (s[i] == '_') white.push_back(i+1);
        if (s[i] == 'X') black.push_back(i+1);
    }
    white.push_back(n+1);
    for (int i = 1; i < white.size(); i++)  {
        int len = white[i] - white[i-1] - 1;
        if (len < c[1]) {
            continue;
        }
        pre[1] = white[i-1]+1;
        break;
    }
    for (int i = white.size()-1; i > 0; i--) {
        int len = white[i] - white[i-1] - 1;
        if (len < c[k]) continue;
        suf[k] = white[i]-1;
        break;
    }
    bool changed = 1;
    while(changed) {
        changed = 0;
        for (int i = 2; i <= k; i++) {
            int st = pre[i-1]+c[i-1]+1, end = st + c[i]-1;
            int tmp = st;
            while(1) {
                auto it = lower_bound(white.begin(), white.end(), st);
                if (*it <= end) {
                    st = *it+1;
                    end = st + c[i]-1;
                } else break;
            }
            pre[i] = max(pre[i], st);
        }
        for (int i = k-1; i >= 1; i--) {
            int end = suf[i+1] - c[i+1] - 1, st = end - c[i] + 1;
            int tmp = end;
            while(1) {
                auto it = lower_bound(white.begin(), white.end(), st);
                if (*it <= end) {
                    end = *it-1;
                    st = end - c[i] + 1;
                } else break;
            }
            suf[i] = min(suf[i], end);
        }
        
        for (int i = 0; i < black.size(); i++) {
            int pos = black[i], cnt = 0, A, B, len, I;
            for (int j = 1; j <= k; j++) {
                int a = pre[j], b = suf[j];
                if (a > pos) break;
                if (a <= pos && pos <= b) {
                    cnt++;
                    A = a, B = b, len = c[j], I = j;
                }
            }
            if (cnt == 1) {
                int a1 = max(1, pos - len + 1), b1 = min(n, pos + len - 1);
                if (a1 > A || b1 < B) {
                    changed = 1;
                    A = max(A, a1);
                    B = min(B, b1);
                    pre[I] = A, suf[I] = B;
                }
            }
        }    
    }
    for (int i = 0; i < pre[1]; i++) ans[i] = '_';
    for (int i = suf[k]+1; i <= n; i++) ans[i] = '_';
    for (int i = 1; i <= k; i++) {
        int len = suf[i] - pre[i] + 1;
        if (len >= c[i] * 2) continue;
        if (len == c[i]) 
            for (int j = pre[i]; j <= suf[i]; j++) ans[j] = 'X';
        
        int len1 = c[i] * 2 - len;
        for (int j = 0; j < len1; j++) {
            ans[j + c[i] - len1 + pre[i]] = 'X';
        }
    }
    for (int i = 2; i <= k; i++) {
        int a = pre[i-1], b = suf[i-1];
        int a1 = pre[i], b1 = suf[i];
        for (int j = b+1; j < a1; j++) ans[j] = '_';
    }
    for (int i = 1; i < white.size() && white.size() != 2; i++) {
        int st = white[i-1]+1, end = white[i]-1;
        bool x = 0;
        for (int j = 1; j <= k; j++) {
            int a = pre[j], b = suf[j], len1 = c[j];
            int a1 = max(st, pre[j]), b1 = min(b, end), len = b1 - a1 + 1;
            if (len >= len1) {
                x = 1;
                break;
            }
        }
        if (!x) {
            for (int j = st; j <= end; j++) ans[j] = '_';
        }
    }
    ans = ans.substr(1, n);
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 1; i < white.size(); i++)  {
      |                     ~~^~~~~~~~~~~~~~
paint.cpp:41:17: warning: unused variable 'tmp' [-Wunused-variable]
   41 |             int tmp = st;
      |                 ^~~
paint.cpp:53:17: warning: unused variable 'tmp' [-Wunused-variable]
   53 |             int tmp = end;
      |                 ^~~
paint.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int i = 0; i < black.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
paint.cpp:99:13: warning: unused variable 'a' [-Wunused-variable]
   99 |         int a = pre[i-1], b = suf[i-1];
      |             ^
paint.cpp:100:26: warning: unused variable 'b1' [-Wunused-variable]
  100 |         int a1 = pre[i], b1 = suf[i];
      |                          ^~
paint.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (int i = 1; i < white.size() && white.size() != 2; i++) {
      |                     ~~^~~~~~~~~~~~~~
paint.cpp:107:17: warning: unused variable 'a' [-Wunused-variable]
  107 |             int a = pre[j], b = suf[j], len1 = c[j];
      |                 ^

• 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