Submission #535440

#	Time	Username	Problem	Language	Result	Execution time	Memory
535440		mario05092929	Paint By Numbers (IOI16_paint)	C++14	100 / 100	391 ms	162244 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <ll,ll> pi;
typedef vector <int> vec;
const ll INF = 1e18;
char s[200005];
int a[200005],pwh[200005],pbl[200005],canbl[105][200005],canbr[105][200005];
int n,k,canX[200005];
bool can_[200005];

string solve_puzzle(string S,vec c) {
    n = S.length(), k = c.size();
    for(int i = 0;i < n;i++) {
        s[i+1] = S[i];
        pwh[i+1] = pwh[i]+(s[i+1] == '_');
        pbl[i+1] = pbl[i]+(s[i+1] == 'X');
    }
    canbl[0][0] = 1;
    for(int i = 0;i < k;i++) a[i+1] = c[i];
    for(int i = 0;i <= k;i++) {
        if(i == 1) {
            for(int j = 0;j <= n+1;j++) canbl[i][j] = 0;
            for(int j = a[i];j <= n;j++) if(pbl[j-a[i]] == 0&&pwh[j] == pwh[j-a[i]]) canbl[i][j] = 1;
        }
        for(int j = 0;j <= n;j++) {
            //cout << canbl[i][j] << ' ';
            if(canbl[i][j]&&s[j+1] != 'X') {
                canbl[i][j+1] = 1;
                if(i == k||i == 0) continue;
                if(j+a[i+1]+(i>0) <= n&&pwh[j+a[i+1]+(i>0)] == pwh[j+(i>0)]) canbl[i+1][j+a[i+1]+(i>0)] = 1;
            }
        }
        //cout << '\n';
    }
    //cout << '\n';
    canbr[k+1][n+1] = 1;
    for(int i = k+1;i >= 1;i--) {
        if(i == k) {
            for(int j = 0;j <= n+1;j++) canbr[i][j] = 0;
            for(int j = n-a[i]+1;j >= 1;j--) if(pbl[j+a[i]-1] == pbl[n]&&pwh[j-1] == pwh[j+a[i]-1]) canbr[i][j] = 1;
        }
        for(int j = n+1;j >= 1;j--) {
            //cout << canbr[i][j] << ' ';
            if(canbr[i][j]&&s[j-1] != 'X') {
                canbr[i][j-1] = 1;
                if(i == 1||i == k+1) continue;
                if(j-a[i-1]-(i<k+1) >= 1&&pwh[j-a[i-1]-(i<k+1)-1] == pwh[j-1-(i<k+1)]) canbr[i-1][j-a[i-1]-(i<k+1)] = 1;
            }
        }
        //cout << '\n';
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 0;j <= k;j++) {
            if(canbl[j][i-1]&&canbr[j+1][i+1]&&s[i] != 'X') can_[i] = 1;
        }
        //cout << i << ' ' << can_[i] << '\n';
    }
    for(int i = 1;i <= k;i++) {
        for(int j = a[i];j <= n;j++) {
            bool bl,br;
            if(j-a[i] <= 0) bl = (i == 1);
            else bl = (canbl[i-1][j-a[i]-1]&&s[j-a[i]] != 'X');
            if(j == n) br = (i == k);
            else br = (canbr[i+1][j+2]&&s[j+1] != 'X');
            if(bl&&br&&pwh[j] == pwh[j-a[i]]) canX[j-a[i]+1]++, canX[j+1]--;
        }
    }
    for(int i = 1;i <= n;i++) canX[i] += canX[i-1];//, cout<< canX[i] << ' ';
   // cout << '\n';
    string ans;
    for(int i = 1;i <= n;i++) {
        if(s[i] != '.') ans += s[i];
        else if(canX[i]&&can_[i]) ans += '?';
        else if(canX[i]) ans += 'X';
        else if(can_[i]) ans += '_';
        else while(1);// cout << i << ' ' << "WTF\n";
    }
    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