제출 #1191101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191101		jasonic	Paint By Numbers (IOI16_paint)	C++20	59 / 100	70 ms	167140 KiB

paint

/*

cnt[i][j] = how many ways to use the first j blocks such that they fit in the first i of the row

idea: bfs each state. count the # of ways to do it at the end (:= a). then use an array to track, for each cell "okay, this is how many times this cell appears". preprocess this using a difference array for sweet sweet O(n)

for each cell, if its == 0, then its guaranteed '.'
               if its == a, then its guaranteed '#'


            
*/

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

#define ll long long
#define one first
#define two second
#define cerr if(0) cout

const int mxn = 200005;
const int mxk = 105;
int cnt[mxn][mxk];
int cnt2[mxn][mxk];
int times[mxn];
int cantplace[mxn];
int haveplace[mxn];
int n, k;

string solve_puzzle(string s, vector<int> c) {
    // calculate ways
    n = s.size();
    k = c.size();

    memset(cnt, 0, sizeof(cnt));
    memset(cnt2, 0, sizeof(cnt2));
    memset(haveplace, 0, sizeof(haveplace));
    memset(cantplace, 0, sizeof(cantplace));
    memset(times, 0, sizeof(times));

    for(int i = 0; i < n; i++) {
        if (s[i] == 'X') haveplace[i+1] += 1;
        if (s[i] == '_') cantplace[i+1] += 1;
        if(i) {haveplace[i+1] += haveplace[i]; cantplace[i+1] += cantplace[i];}
    }

    cnt[0][0] = 1;
    // dp[i][j] = dp[i + c[j]]
    for(int i = 1; i <= n && s[i-1] != 'X'; i++) cnt[i][0] = 1;

    for(int right = 0; right <= n; right++) cerr << 0 << ' ' << right << ' ' << cnt[right][0] << '\n';

    for(int i = 1; i <= k; i++) {
        int blockLength = c[i-1];
        
        for(int right = 1; right <= n; right++) {
            cnt[right][i] += cnt[right-1][i]; // just append

            int left = right - blockLength + 1; // this is where the "block of X" will get put

            if(left < 1) continue;

            // one indexed everything LOL
            if(cantplace[right] == cantplace[left - 1]) { // no "_" in the range
                if(left >= 2) if(s[left - 2] == 'X') {
                    cerr << "exit1\n";
                    cerr << i << ' ' << right << ' ' << cnt[right][i] << '\n';
                    continue;
                }
                if(right < n) if(s[right] == 'X') {
                    cerr << "exit2\n";
                    cerr << i << ' ' << right << ' ' << cnt[right][i] << '\n';
                    continue;
                }

                cnt[right][i] += cnt[max(0, left-2)][i-1];
            }

            cerr << max(0, left-2) << '\n';

            cerr << i << ' ' << right << ' ' << cnt[right][i] << '\n';
        }
    }

    cnt2[n+1][k+1] = 1;
    for(int i = n; i >= 1 && s[i-1] != 'X'; i--) cnt2[i][k+1] = 1;

    // other way!
    for(int i = k; i >= 1; i--) {
        int blockLength = c[i-1];
        
        for(int left = n; left >= 1; left--) {
            cnt2[left][i] += cnt2[left+1][i]; // just append
            int right = left + blockLength - 1;

            if(right >= n+1) continue;

            if(cantplace[left-1] == cantplace[right]) {
                if(left >= 2) if(s[left - 2] == 'X') {
                    cerr << "exit1\n";
                    cerr << i << ' ' << right << ' ' << cnt[right][i] << '\n';
                    continue;
                }
                if(right < n) if(s[right] == 'X') {
                    cerr << "exit2\n";
                    cerr << i << ' ' << right << ' ' << cnt[right][i] << '\n';
                    continue;
                }
                cnt2[left][i] += cnt2[min(n+1, right+2)][i+1];
            }

            cerr << i << ' ' << left << ' ' << right << ' ' << cnt2[left][i] << '\n';
        }
    }

    for(int i = 1; i <= k; i++) {
        int blockSize = c[i-1];
        for(int left = 1; left <= n; left++) {
            int right = left + blockSize - 1;
            if(right > n) continue;

            if(cantplace[left-1] != cantplace[right]) continue;
            if(left >= 2) if(s[left-2] == 'X') continue;
            if(right < n) if(s[right] == 'X') continue;

            int timesUsed = cnt[max(0, left-2)][i-1] * cnt2[min(n+1, right+2)][i+1];
            
            times[left-1] += timesUsed;
            if(right < n) times[right] -= timesUsed;
        }
    }

    for(int i = 1; i < n; i++) {
        times[i] += times[i-1];
    }

    for(int i = 0; i < n; i++) cerr << times[i] << ' ';
    
    string ans;
    for(int i = 0; i < n; i++) {
        if(times[i] == 0) ans.push_back('_');
        else if(times[i] == cnt[n][k]) ans.push_back('X');
        else ans.push_back('?');
    }

    return ans;
}

컴파일 시 표준 에러 (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