Submission #479657

#	Time	Username	Problem	Language	Result	Execution time	Memory
479657		ponytail	Paint By Numbers (IOI16_paint)	C++17	100 / 100	572 ms	358376 KiB

paint

#include "paint.h"
 
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <bits/stdc++.h>
 
 
using namespace std;
 
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int k = c.size();
    int n = s.size();
    int ps[2][n]; // X _
    ps[0][0] = (s[0] == 'X');
    ps[1][0] = (s[0] == '_');
    for(int i=1; i<n; i++) {
        ps[0][i] = ps[0][i-1] + (s[i] == 'X');
        ps[1][i] = ps[1][i-1] + (s[i] == '_');
    }
    int can[2][n]; // X _
    for(int i=0; i<2; i++) {
        for(int j=0; j<n; j++) {
            can[i][j] = 0;
        }
    }
    int mx[n];
    int prv = 0;
    for(int i=0; i<n; i++) {
        if(s[i] == 'X') prv = i;
        mx[i] = prv;
    }
    int mx2[n];
    prv = n-1;
    for(int i=n-1; i>=0; i--) {
        if(s[i] == 'X') prv = i;
        mx2[i] = prv;
    }
    bool dp_forward[k][n];
    bool dp_backward[k][n];
    for(int i=0; i<k; i++) {
        for(int j=0; j<n; j++) {
            dp_forward[i][j] = dp_backward[i][j] = 0;
        }
    }
 
    int dp_forsum[k][n];
    int dp_backsum[k][n];
    for(int i=0; i<k; i++) {
        for(int j=0; j<n; j++) {
            dp_forsum[i][j] = dp_backsum[i][j] = 0;
        }
    }
    
    int real_dp[k][n]; // The real answer to question "i-th black segment ENDING at j-th column?"
    int real_sum[k][n];
    for(int i=0; i<k; i++) {
        for(int j=0; j<n; j++) {
            real_dp[i][j] = 0;
            real_sum[i][j] = 0;
        }
    }
    
    for(int i=c[0]-1; i<n; i++) {
        if(ps[1][i] - (i == c[0] - 1 ? 0 : ps[1][i - c[0]]) == 0) {
            if(i == c[0] - 1 || ps[0][i - c[0]] == 0) {
                dp_forward[0][i] = 1;
            }
        }
        dp_forsum[0][i] = (i == 0 ? 0 : dp_forsum[0][i-1]) + dp_forward[0][i];
    }
    int cum = c[0] + 1;
    for(int i=1; i<k; i++) {
        cum += c[i];
        for(int j=cum-1; j<n; j++) {
            if(ps[1][j] - ps[1][j-c[i]] > 0) {
                dp_forsum[i][j] = dp_forsum[i][j-1] + dp_forward[i][j];
                continue;
            }
            if(s[j - c[i]] == 'X') {
                dp_forsum[i][j] = dp_forsum[i][j-1] + dp_forward[i][j];
                continue;
            }
            dp_forward[i][j] = (dp_forsum[i-1][j-c[i]-1] - (mx[j-c[i]] == 0 ? 0 : dp_forsum[i-1][mx[j-c[i]]-1]) > 0);
            dp_forsum[i][j] = dp_forsum[i][j-1] + dp_forward[i][j];
        }
        cum++;
    }
    
    for(int i=0; i<n - c[k-1] + 1; i++) {
        if(ps[1][i + c[k-1] - 1] - (i > 0 ? ps[1][i-1] : 0) == 0) {
            if(ps[0][n-1] - ps[0][i + c[k-1] - 1] == 0) {
                dp_backward[k-1][i] = 1;
            }
        }
        dp_backsum[k-1][i] = (i == 0 ? 0 : dp_backsum[k-1][i-1]) + dp_backward[k-1][i];
    }
    for(int i=n-c[k-1]+1; i<n; i++) {
        dp_backsum[k-1][i] = (i == 0 ? 0 : dp_backsum[k-1][i-1]) + dp_backward[k-1][i];
    }
    cum = c[k-1] + 1;
    for(int i=k-2; i>=0; i--) {
        cum += c[i] - 1;
        for(int j=0; j<n-cum; j++) {
            if(ps[1][j + c[i] - 1]-(j > 0 ? ps[1][j-1] : 0) > 0) {
                dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
                continue;
            }
            if(s[j + c[i]] == 'X') {
                dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
                continue;
            }
            dp_backward[i][j] = (dp_backsum[i+1][mx2[j + c[i]]] - dp_backsum[i+1][j+c[i]] > 0);
            dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
        }
        for(int j=n-cum; j<n; j++) {
            dp_backsum[i][j] = (j==0 ? 0 : dp_backsum[i][j-1]) + dp_backward[i][j];
        }
        cum += 2;
    }
    
    for(int i=0; i<k; i++) {
        for(int j=0; j<n; j++) {
            if(j+1<n && s[j+1] == 'X') {
                real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
                continue;
            }
            if(j == n-1) {
                if(i == k-1) real_dp[i][j] = dp_forward[i][j];
                real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
                continue;
            }
            if(i == k-1) {
                real_dp[i][j] = dp_forward[i][j] && (ps[0][n-1] - ps[0][j] == 0);
                real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
                continue;
            }
            real_dp[i][j] = dp_forward[i][j] && (dp_backsum[i+1][mx2[j+1]] - dp_backsum[i+1][j+1] > 0);
            real_sum[i][j] = (j == 0 ? 0 : real_sum[i][j-1]) + real_dp[i][j];
            if(real_dp[i][j]) assert(s[j] != '_');
        }
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<k; j++) {
            if(real_sum[j][min(n-1, i+c[j]-1)] - (i==0 ? 0 : real_sum[j][i-1]) > 0) {
                can[0][i] = 1;
            }
        }
        for(int j=0; j<k-1; j++) {
            if(s[i] != 'X' && i>0 && dp_forsum[j][i-1] - (mx[i-1] == 0 ? 0 : dp_forsum[j][mx[i-1] - 1]) > 0 && i + c[j+1] < n && (dp_backsum[j+1][mx2[i]] - dp_backsum[j+1][i] > 0)) {
                can[1][i] = 1;
               // if(i == 4)cout << j<<"\n";
            }
        }
        if(s[i] != 'X' && dp_backsum[0][mx2[i]] - dp_backsum[0][i] > 0 && (i == 0 || ps[0][i-1] == 0)) {
            can[1][i] = 1;
         //   if(i==4) cout<<"A\n";
        }
        if(s[i] != 'X' && i > 0 && real_sum[k-1][i-1] && ps[0][n-1] - ps[0][i] == 0) {
            can[1][i] = 1;
          //  if(i==4) cout<<"B\n";
        }
    }
    
    for(int i=0; i<k; i++) {
        for(int j=0; j<n; j++) {
            if(real_dp[i][j]) assert(s[j] != '_');
        }
    }
    string ans;
    for(int i=0; i<n; i++) {
        if(can[0][i] && can[1][i]) ans += "?";
        else if(can[0][i]) ans += "X";
        else ans += "_";
    }
    for(int i=0; i<n; i++) {
        assert(!(s[i] == 'X' && ans[i] != 'X'));
        assert(!(s[i] == '_' && ans[i] != '_'));
    }
    return ans;
}

• 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