Submission #1021911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021911		vjudge1	Paint By Numbers (IOI16_paint)	C++17	100 / 100	178 ms	45816 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

int a[200100];
int pref[200100][2], suf[200100];
int ok[200100][2];
int c[200100];
bool dpref[200100][101], dsuf[200100][101];


string solve_puzzle(string s, vector<int> C) {
    int k = C.size();
    int n = s.size();
    for(int i=0; i<k; i++){
        c[i+1] = C[i];
    }
    for(int i=0; i<n; i++){
        if(s[i] == 88) a[i + 1] = 1;
        if(s[i] == 95) a[i + 1] = 0;
        if(s[i] == 46) a[i + 1] = -1;
    }
    for(int i=1; i<=n; i++){
        pref[i][0] = pref[i-1][0] + (a[i] == 0);
    }
    for(int i=1; i<=n; i++){
        pref[i][1] = pref[i-1][1] + (a[i] == 1);
    }
    dpref[0][0] = 1;
    for(int i=0; i<=n; i++){
        for(int j=0; j<=k; j++){
            if(!dpref[i][j]) continue;
            if(i + 1 <= n and a[i + 1] != 1) dpref[i + 1][j] = 1;
            if(j + 1 <= k and i + c[j + 1] + 1 <= n and pref[i + c[j + 1]][0] - pref[i][0] == 0 and a[i + c[j + 1] + 1] != 1) dpref[i + 1 + c[j + 1]][j + 1] = 1;
        }
    }
    dsuf[n+1][k+1] = 1;
    for(int i=n+1; i>=1; i--){
        for(int j=1; j<=k+1; j++){
            if(!dsuf[i][j]) continue;
            if(i - 1 >= 1 and a[i - 1] != 1) dsuf[i - 1][j] = 1;
            if(j - 1 >= 1 and i - c[j - 1] - 1 >= 1 and pref[i-1][0] - pref[i-c[j-1]-1][0] == 0 and a[i - c[j - 1] - 1] != 1) dsuf[i - 1 - c[j - 1]][j-1] = 1;
        }
    }
    int g = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            if(i + c[j] - 1 > n) continue;
            if(pref[i+c[j]-1][0]-pref[i-1][0] == 0 and dpref[i-1][j-1] and dsuf[i+c[j]][j+1]) g = max(g, i+c[j]-1);
        }
        if(i <= g) ok[i][1] = 1;
    }
    //for(int i=1; i<=n; i++) cout<<dsuf[i][2];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            if(dpref[i][j] and dsuf[i][j+1] and a[i] != 1) ok[i][0] = 1;
            if(dpref[i][j-1] and dsuf[i][j] and a[i] != 1) ok[i][0] = 1;
        }
    }
    string ans;
    for(int i=1; i<=n; i++){
        char c;
        if(ok[i][1] and ok[i][0]) c = '?';
        else if(ok[i][1]) c = 'X';
        else c = '_';
        ans.pb(c);
    }
            

    
    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