Submission #706406

#	Time	Username	Problem	Language	Result	Execution time	Memory
706406		rafatoa	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1125 ms	175844 KiB

paint

#include <bits/stdc++.h>
using namespace std;
 
string solve_puzzle(string s, vector<int> c){
    if(s.size() == 1) return "X"; //Caso bomba :)
 
    int n = s.size(), k = c.size();
    c.insert(c.begin(), 0); //Pasar c a 1-index
    c.push_back(0);
 
    vector<int> pw(n+1), pb(n+1);
    for(int i=0; i<n; i++){
        pw[i+1] = pw[i]+(s[i] == '_' ? 1 : 0);
        pb[i+1] = pb[i]+(s[i] == 'X' ? 1 : 0);
    }
 
    //
    auto wh = [&](int l, int r){
        return pw[r+1]-pw[l];
    };
    auto bl = [&](int l, int r){
        return pb[r+1]-pb[l];
    };
 
    //
    vector<vector<int>> l(n, vector<int>(k+2)), r(n, vector<int>(k+2));
    for(int i=0; i<n; i++){
        if(bl(0, i) == 0) l[i][0] = 1;
        if(bl(i, n-1) == 0) r[i][k+1] = 1;
    }
 
    for(int j=1; j<=k; j++)
    for(int i=0; i<n; i++){
        if(i-1 >= 0 && s[i] != 'X') l[i][j] |= l[i-1][j];
        if(i+c[j]-1 < n && ((i-2 < 0 && j == 1) || (i-2 >= 0 && l[i-2][j-1])) &&
        wh(i, i+c[j]-1) == 0 && (i-1 < 0 || s[i-1] != 'X') && (i+c[j] >= n || s[i+c[j]] != 'X')){
            //cerr << i+c[j]-1 << " " << j << "\n";
            l[i+c[j]-1][j] = 1;
        }
    }
    
    for(int j=k; j>=1; j--)
    for(int i=n-1; i>=0; i--){
        if(i+1 < n && s[i] != 'X') r[i][j] |= r[i+1][j];
        if(i-c[j]+1 >= 0 && ((i+2 >= n && j == k) || (i+2 < n && r[i+2][j+1])) &&
        wh(i-c[j]+1, i) == 0 && (i+1 >= n || s[i+1] != 'X') && (i-c[j] < 0 || s[i-c[j]] != 'X')){
            //cerr << i-c[j]+1 << " " << j << "\n";
            r[i-c[j]+1][j] = 1;
        }
    }
 
    string ans = string(n, '?');
    for(int i=0; i<n; i++){
        bool ok = 0;
        if(i == 0) ok = r[i+1][1];
        else if(i == n-1) ok = l[i-1][k];
        else {
            for(int j=0; j<=k && !ok; j++)
                ok |= (l[i-1][j] && r[i+1][j+1]);
        }
 
        if(!ok || s[i] == 'X') ans[i] = 'X';
    }
 
    vector<int> pr(n+1);
    for(int j=1; j<=k; j++)
    for(int i=0; i<n; i++){
        if(i+c[j]-1 < n && ((i-2 < 0 && j == 1) || (i-2 >= 0 && l[i-2][j-1])) && ((i+c[j]+1 >= n && j == k) || (i+c[j]+1 < n && r[i+c[j]+1][j+1])) &&
        (i-1 < 0 || s[i-1] != 'X') && (i+c[j] >= n || s[i+c[j]] != 'X') && wh(i, i+c[j]-1) == 0){
            pr[i]++; pr[i+c[j]]--;
        }
    }
 	
  	for(int i=1; i<=n; i++) pr[i] += pr[i-1];
    for(int i=0; i<n; i++)
        if(pr[i] == 0 || 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