제출 #802867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802867		HaroldVemeno	Paint By Numbers (IOI16_paint)	C++17	100 / 100	436 ms	43508 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using ull = unsigned long long;
using ll = long long;

char dpl[200001][101];
char dpr[200001][101];
int ups[200001];
bool ugd[200000];
int dxgd[200001];
int xgd[200000];

std::string solve_puzzle(string s, vector<int> c) {
    D(s)
    int n = s.size();
    int k = c.size();
    ups[0] = 0;
    for(int i = 0; i < n; ++i) {
        ups[i+1] = ups[i] + (s[i] == '_');
    }

    dpl[0][0] = 2;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j <= k; ++j) {
            if(!dpl[i][j]) continue;
            if(dpl[i][j] == 2 && j < k && i + c[j] <= n) {
                if(ups[i+c[j]] - ups[i] == 0) {
                    if(i+c[j] == n || s[i+c[j]] != 'X') {
                        dpl[i+c[j]][j+1] = 1;
                    }
                }
            }
            if(s[i] != 'X') {
                dpl[i+1][j] = 2;
            }
        }
    }
    dpr[0][0] = 2;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j <= k; ++j) {
            if(!dpr[i][j]) continue;
            if(dpr[i][j] == 2 && j < k && i + c[k-1-j] <= n) {
                if(ups[n-i] - ups[n-i-c[k-1-j]] == 0) {
                    if(i+c[k-1-j] == n || s[n-1-i-c[k-1-j]] != 'X') {
                        dpr[i+c[k-1-j]][j+1] = 1;
                    }
                }
            }
            if(s[n-1-i] != 'X') {
                dpr[i+1][j] = 2;
            }
        }
    }

    for(int i = 0; i < n; ++i) {
        if(s[i] == 'X') continue;
        for(int j = 0; j <= k; ++j) {
            if(dpl[i][j] && dpr[n-1-i][k-j]) {
                ugd[i] = true;
                break;
            }
        }
    }
    for(int j = 0; j < k; ++j) {
        for(int i = 0; i <= n-c[j]; ++i) {
            if(ups[i+c[j]] - ups[i] > 0) continue;
            if(dpl[i][j] == 2 && dpr[n-c[j]-i][k-j-1] == 2) {
                ++dxgd[i];
                --dxgd[i+c[j]];
                continue;
            }
        }
    }
    xgd[0] = dxgd[0];
    for(int i = 1; i < n; ++i) {
        xgd[i] = xgd[i-1] + dxgd[i];
    }
    string out;
    for(int i = 0; i < n; ++i) {
        if(xgd[i] && ugd[i]) {
            out.push_back('?');
        } else if(xgd[i]) {
            out.push_back('X');
        } else if(ugd[i]) {
            out.push_back('_');
        }
    }

    ifdeb {
        cerr << '\n';
        for(int i = 0; i <= n; ++i) {
            cerr << ups[i] << ' ';
        }
        cerr << '\n' << '\n';
        for(int i = 0; i <= n; ++i) { for(int j = 0; j <= k; ++j) {
                cerr << dpl[i][j] << ' ';
            }
            cerr << '\n';
        }
        cerr << '\n';
        for(int i = 0; i <= n; ++i) { for(int j = 0; j <= k; ++j) {
                cerr << dpr[i][j] << ' ';
            }
            cerr << '\n';
        }
        cerr << '\n';
        for(int i = 0; i < n; ++i) {
            cerr << ugd[i] << ' ';
        }
        cerr << '\n' << '\n';
        for(int i = 0; i < n; ++i) {
            cerr << xgd[i] << ' ';
        }
        cerr << '\n' << '\n';
    }

    return out;

}

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