Submission #866791

#	Time	Username	Problem	Language	Result	Execution time	Memory
866791		hgmhc	Paint By Numbers (IOI16_paint)	C++17	0 / 100	0 ms	348 KiB

paint

#pragma region template
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(x) cerr << #x << ": " << (x) << endl;
#pragma endregion template

// 관찰 1-1. 어떤 ?의 인덱스 i에 대해, 문자를 X로 대체 불가능 <-> 문자가 _로 고정
// 관찰 1-2. 어떤 ?의 인덱스 i에 대해, 문자를 _로 대체 불가능 <-> 문자가 X로 고정
// 관찰 1-3. 어떤 ?의 인덱스 i에 대해, 그런거 없으면 그냥 ?

// 생각 1. "....."꼴은 편하게 풀 수 있다
// 생각 2. X 또는 _가 개입하는 순간 불편한 사항이 많아진다
// 생각 3. 불편한 것들에 집중하여 고민해보자
// 생각 4. 결국 full 솔루션은 nk+nlog 같은거? 정도 허용할 것 같다
// 생각 5. 파라매트릭 서치가 유용한 상황이 발생할 수 있을 것 같으니 지속적으로 의식하자

// 보조풀이 1. 어떤 ?의 인덱스 i에 대해, 문자가 X로 고정될 조건은,
//   - 즉 문자를 _로 대체 불가능함은,
//   - p(i) := 1..i를 앞쪽 블록들로 valid하게 구성할 때, 사용할 수 있는 블록의 최댓값
//   - s(i) := i..n를 뒷쪽 블록들로 valid하게 구성할 때, 사용할 수 있는 블록의 최댓값
//   - 전처리에는 O(nk) 정도 소요될 것 같다
//   - ..일때, p(i-1)+s(i+1) < k라는 것과 동치이다

// 보조풀이 2. 어떤 ?의 인덱스 i에 대해, 문자가 _로 고정될 조건은,
//   - 즉 문자를 X로 대체 불가능함은,
//   - 모든 x=1..k에 대해
//     - i를 포함하는 모든 길이가 c[x]인 구간 [s,e]에 대해서
//       - S[s-1] != 'X' && S[e+1] != 'X'이며,
//       - S[s],..,S[e] != '_' 이며,
//       - p(s-2) >= x-1 && s(e+2) >= k-x
//     - ..라는 조건이 하나도 만족하지 않음
//   - 을 만족함을 의미한다
//   - 모든 구간을 둘러보는 것은 오래 걸린다
//   - sum c의 bound가 n이므로 인덱스당 n만큼 걸린다
//   - 그래도 나름 이 정도면 90점이 나오겠으니 해보자!

const int N = 5005, K = 105;
int n, k;
int cX[N], c_[N];
char S[N];
int c[N];

bool can_set_all_X(int l, int r) {
    if (1 <= l && l <= r && r <= n)
        return c_[r] - c_[l-1] == 0;
    else return false;
}

int p(int i) {
    static bool ready[N]{};
    static int dp[N]{};
    if (i == -1) return 0;
    if (i == 0) return 0;
    if (ready[i]) return dp[i];
    ready[i] = true;

    dp[i] = p(i-1);
    if (dp[i] == k) return dp[i];
    // challenge for dp[i]+1
    int x = dp[i]+1; // c[x]

    if (i-c[x] < 0) return dp[i];
    if (S[ i-c[x] ] == 'X') return dp[i];
    if (!can_set_all_X(i-c[x]+1, i)) return dp[i];

    if (i-c[x] == 0) {
        if (dp[i] == 0) return ++dp[i];
        return dp[i];
    }
    assert(i-c[x] > 0);
    if (p(i-c[x]-1) == dp[i]) {
        return ++dp[i];
    }
    return dp[i];
}

int s(int i) {
    static bool ready[N]{};
    static int dp[N]{};
    if (i == n+2) return 0;
    if (i == n+1) return 0;
    if (ready[i]) return dp[i];
    ready[i] = true;

    dp[i] = s(i+1);
    if (dp[i] == k) return dp[i];
    // challenge for dp[i]+1
    int x = k-dp[i];

    if (i+c[x] > n+1) return dp[i];
    if (S[ i+c[x] ] == 'X') return dp[i];
    if (!can_set_all_X(i, i+c[x]-1)) return dp[i];

    if (i+c[x] == n+1) {
        if (dp[i] == 0) return ++dp[i];
        return dp[i];
    }
    assert(i+c[x] < n+1);
    if (s(i+c[x]+1) == dp[i]) {
        return ++dp[i];
    }
    return dp[i];
}

void precalc(const string &s, const vi &c) {
    n = siz(s), k = siz(c);
    rep(i,1,n) S[i] = s[i-1];
    rep(i,1,k) ::c[i] = c[i-1];
    rep(i,1,n+2) cX[i] = cX[i-1]+(S[i]=='X');
    rep(i,1,n+2) c_[i] = c_[i-1]+(S[i]=='_');
}

bool fixX(int i) {
    assert(i-1 >= -1 && i+1 <= n+2);
    return p(i-1)+s(i+1) < k;
}

bool fix_(int i) {
    rep(x,1,k) {
        for (int s = i-c[x]+1, e = i; s <= i && i <= e; s++, e++) {
            if (s < 1) continue;
            if (e > n) break;
            if (S[s-1] != 'X' && S[e+1] != 'X') {
                if (can_set_all_X(s,e)) {
                    // cerr << "[s,e]: " << s << ' ' << e << endl;
                    // cerr << "[x-1,k-x]: " << x-1 << ' ' << k-x << endl;
                    if (p(s-2) >= x-1 && ::s(e+2) >= k-x) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

string solve_puzzle(string a, vi c) {
    string res(n,'$');
    precalc(a,c);

    rep(i,1,n) {
        if (S[i] != '.') {
            res[i-1] = S[i];
            continue;
        }
        if (fixX(i)) res[i-1] = 'X';
        else if (fix_(i)) res[i-1] = '_';
        else res[i-1] = '?';
    }
    
    // rep(i,0,n) cerr << S[i] << ' ';
    // cerr << endl;
    // rep(i,0,n) cerr << p(i) << ' ';
    // cerr << endl;
    // rep(i,0,n) cerr << s(i) << ' ';
    // cerr << '\n' << res;

    return res;
}

#pragma region grader
#ifdef LOCAL

const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];

int main() {
    assert(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(1 == scanf("%d", &c[i]));
    }
    std::string ans = solve_puzzle(s, c);
    
    printf("%s\n", ans.data());
    return 0;
}

#endif
#pragma endregion grader

Compilation message (stderr)

paint.cpp:1: warning: ignoring '#pragma region template' [-Wunknown-pragmas]
    1 | #pragma region template
      | 
paint.cpp:13: warning: ignoring '#pragma endregion template' [-Wunknown-pragmas]
   13 | #pragma endregion template
      | 
paint.cpp:169: warning: ignoring '#pragma region grader' [-Wunknown-pragmas]
  169 | #pragma region grader
      | 
paint.cpp:191: warning: ignoring '#pragma endregion grader' [-Wunknown-pragmas]
  191 | #pragma endregion grader
      |

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