Submission #426373

#	Time	Username	Problem	Language	Result	Execution time	Memory
426373		zoooma13	Paint By Numbers (IOI16_paint)	C++14	100 / 100	529 ms	59320 KiB

paint

#include "bits/stdc++.h"
#include "paint.h"
using namespace std;

#define MAX_N 200005
#define MAX_K 102

int N ,K;
string board;
vector <int> wh ,bl ,block;
bool check(int l ,int r){
    if(r >= N)
        return false;
    if(wh[r+1] != wh[l])
        return false;
    if(r+1 < N && board[r+1] == 'X')
        return false;
    return true;
}

bool can_white[MAX_N];
int can_black[MAX_N];

bool vis[MAX_K][MAX_N];
bool can[MAX_K][MAX_N];
bool go(int i ,int j){
    if(i >= N)
        return j == K;
    bool&good = can[j][i];
    if(vis[j][i])
        return good;
    vis[j][i] = true;

    if(board[i] != 'X' && go(i+1 ,j)){
        good = true;
        can_white[i] = true;
    }
    if(j != K && check(i ,i+block[j]-1) && go(i+block[j]+1 ,j+1)){
        good = true;
        can_black[i]++;
        can_black[i+block[j]]--;
        if(i+block[j] < N)
            can_white[i+block[j]] = true;
    }
    return good;
}

string solve_puzzle(string s, vector<int> c){
    N = s.size();
    K = c.size();
    board = s;
    block = c;
    wh.resize(N+1);
    bl.resize(N+1);
    for(int i = 0; i < N; i++){
        bl[i+1] = bl[i] + (s[i] == 'X');
        wh[i+1] = wh[i] + (s[i] == '_');
    }
    assert(go(0 ,0));
    for(int i = 0; i <= N; i++)
        can_black[i] += (i? can_black[i-1] : 0);
    string ans;
    for(int i = 0; i < N; i++){
        if(can_white[i] && can_black[i])
            ans += '?';
        else if(can_black[i])
            ans += 'X';
        else if(can_white[i])
            ans += '_';
        else
            assert(false);
    }
    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