제출 #296616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296616		Mercenary	Paint By Numbers (IOI16_paint)	C++14	100 / 100	966 ms	129324 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int maxk = 1e2 + 5;


bool dp[maxn][maxk];
bool dp1[maxn][maxk];
int trace[maxn][maxk];

int pre[maxn] , nxt[maxn];
int sum_zero[maxn];
int a[maxn] , b[maxn];
struct dq{
    int a[maxn];
    int l = 1 , r = 0;
    void push_back(int x){
        a[++r] = x;
    }
    int size(){
        return r - l + 1;
    }
    int front(){
        return a[l];
    }
    int back(){
        return a[r];
    }
    void pop_front(){
        ++l;
    }
    void reset(){
        l = 1 , r = 0;
    }
}q;

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n = s.size() , k = c.size();
    if(c.size() == 0)return string(n , '_');
    s = " " + s + " ";
    dp[0][0] = 1;
    dp1[n + 1][0] = 1;
    nxt[n + 1] = n + 1;
    for(int i = 1 ; i <= n ; ++i){
        pre[i] = pre[i - 1];
        if(s[i] == 'X')pre[i] = i;
        sum_zero[i] = sum_zero[i - 1] + (s[i] == '_');
    }
    for(int i = n ; i >= 1 ; --i){
        nxt[i] = nxt[i + 1];
        if(s[i] == 'X')nxt[i] = i;
    }
    for(int i = 1 ; i <= k ; ++i){
        q.reset();
        int cur = c[i - 1];
        for(int j = cur ; j <= n ; ++j){
            if(i == 1 && dp[j - cur][i - 1])q.push_back(j - cur);
            else if(i > 1 && j - cur - 1 >= 0 && dp[j - cur - 1][i - 1])q.push_back(j - cur - 1);
            while(q.size() && q.front() < pre[j - cur])q.pop_front();
            if(q.size() && sum_zero[j] - sum_zero[j - cur] == 0 && (i > 1 || pre[j - cur] == 0))dp[j][i] = 1 , trace[j][i] = q.front();
        }
    }
    for(int i = 1 ; i <= k ; ++i){
        q.reset();
        int cur = c[k - i];
        for(int j = n - cur + 1 ; j >= 1 ; --j){
            if(i == 1 && dp1[j + cur][i - 1])q.push_back(j + cur);
            else if(i > 1 && dp1[j + cur + 1][i - 1])q.push_back(j + cur + 1);
            while(q.size() && q.front() > nxt[j + cur])q.pop_front();
            if(q.size() && sum_zero[j + cur - 1] - sum_zero[j - 1] == 0 && (i > 1 || nxt[j + cur] == n + 1)){
                dp1[j][i] = 1;
                if(dp[j + cur - 1][k - i + 1]){
                    b[j]++;b[j + cur]--;
                    a[j + cur]++;a[q.front()]--;
                    a[trace[j + cur - 1][k - i + 1] + 1]++;a[j]--;
                }
            }
        }
    }
    string res(n , 0);
    for(int i = 1 ; i <= n ; ++i){
        a[i] += a[i - 1];b[i] += b[i - 1];
        if(a[i] && b[i])res[i - 1] = '?';
        else if(a[i])res[i - 1] = '_';
        else res[i - 1] = 'X';
    }
    return res;
}
#ifdef LOCAL
#include "paint.h"

#include <vector>
#include <string>
#include <cstdio>
#include <cassert>

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

int main() {
    freopen("A.INP","r",stdin);
    freopen("A.OUT","w",stdout);
    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

• 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