제출 #562847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
562847		elazarkoren	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	308 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 2e5;
const int MAX_K = 105;

int cnt[MAX_N];
//bool dpl[MAX_N][MAX_K];
//bool dpr[MAX_N][MAX_K];

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n = s.size();
    int k = c.size();
//    for (int i = 0; i < n; i++) {
//        int sum = -1;
//        for (int j = 0; j < k; j++) {
//            sum += c[j] + 1;
//            if (i && dpl[i - 1][j]) {
//                dpl[i][j] = true;
//                continue;
//            }
//            if (sum > i + 1) break;
//        }
//    }
    vi bad;
    for (int i = 0; i < n; i++) {
        if (s[i] == '_') bad.push_back(i);
    }
    bad.push_back(n);
    int sum = 0;
    for (int d : c) sum += d;
    int count = 0;
    for (int j = 0; j <= n; j++, count++) {
        int ind = j;
        vi v;
        for (int l = 0; l < k && ind < n; l++) {
            int d = c[l];
            while (ind < n) {
                int y = *lower_bound(all(bad), ind);
                if (y - ind >= d) break;
                ind = y + 1;
            }
            for (int i = ind; i < min(ind + d, n); i++) {
                v.push_back(i);
            }
            ind += d + 1;
        }
        if (v.size() != sum) break;
        for (int i : v) cnt[i]++;
//        ind = n - 1;
//        for (int l = k - 1; l >= j; l--) {
//            int d = c[l];
//            for (int i = ind; i > ind - d; i--) cnt[i]++;
//            ind -= d + 1;
//        }
    }
    string ans(n, '?');
    for (int i = 0; i < n; i++) {
        if (cnt[i] == count) ans[i] = 'X';
        else if (!cnt[i]) ans[i] = '_';
    }
    return ans;
}

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

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:59:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         if (v.size() != sum) break;
      |             ~~~~~~~~~^~~~~~

• 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