Submission #412860

#	Time	Username	Problem	Language	Result	Execution time	Memory
412860		losmi247	Paint By Numbers (IOI16_paint)	C++14	32 / 100	1 ms	332 KiB

paint

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+45;
const int K = 105;

int n,k;
string s;
int c[K];


int pf[N],suf[N];
string prazna(){
    int sum = 0;
    for(int i = 1; i <= k; i++) sum += c[i];

    if(sum == n-(k-1)){
        string ans = "";
        for(int i = 1; i <= k; i++){
            for(int j = 1; j <= c[i]; j++) ans += 'X';
            if(i < k) ans += '_';
        }
        return ans;
    }

    for(int i = 1; i <= k; i++) pf[i] = pf[i-1]+c[i];
    for(int i = k; i >= 1; i--) suf[i] = suf[i+1]+c[i];

    string ans = s;
    for(int i = 0; i < n; i++){
        /// da li moze da bude X na i?
        bool mozex = 0;
        for(int j = 1; j <= k; j++){
            for(int poc = max(0,i-c[j]+1); poc <= i && poc+c[j]-1 < n; poc++){
                if(pf[j-1]+(j-1) <= poc && suf[j+1]+(k-(j+1)+1) <= n-poc-1) mozex = 1;
            }
        }
        /// da li moze da bude _ na i?
        bool mozey = 0;
        if(k == 1) mozey = (i <= n-1-c[1] || i >= c[1]);
        for(int j = 1; j < k; j++){
            if(pf[j]+(j-1) <= i && suf[j+1]+(k-(j+1)) <= n-i-1) mozey = 1;
        }
        mozey |= (i <= n-(sum+k-1)-1 || i >= sum+k-1);

        if(mozex && mozey) ans[i] = '?';
        else if(mozex) ans[i] = 'X';
        else if(mozey) ans[i] = '_';
    }

    return ans;
}



bool pfdp[K][N],sfdp[K][N];
string novo(){
    int sum = 0;
    for(int i = 1; i <= k; i++) sum += c[i];

    if(sum == n-(k-1)){
        string ans = "";
        for(int i = 1; i <= k; i++){
            for(int j = 1; j <= c[i]; j++) ans += 'X';
            if(i < k) ans += '_';
        }
        return ans;
    }

    for(int i = 1; i <= k; i++) pf[i] = pf[i-1]+c[i];
    for(int i = k; i >= 1; i--) suf[i] = suf[i+1]+c[i];

    for(int i = 0; i <= n; i++) pfdp[0][i] = 1;
    for(int j = 1; j <= k; j++){
        for(int i = 1; i <= n; i++){
            pfdp[j][i] |= pfdp[j][i-1]; /// stavi _ na i
            if(i < c[j]) continue;
            bool moze = 1;
            for(int h = i-c[j]+1; h <= i; h++){ /// stavi j-ti blok tako da se zavrsava na i
                if(s[h-1] == '_') moze = 0;
            }
            pfdp[j][i] |= (moze && pfdp[j-1][i-c[j]]);
        }
    }

    for(int i = n+1; i >= 1; i--) sfdp[k+1][i] = 1;
    for(int j = k; j >= 1; j--){
        for(int i = n; i >= 1; i--){
            sfdp[j][i] |= sfdp[j][i+1]; /// stavi _ na i
            if(n-i+1 < c[j]) continue;
            bool moze = 1;
            for(int h = i; h <= i+c[j]-1; h++){
                if(s[h-1] == '_') moze = 0;
            }
            sfdp[j][i] |= (moze && sfdp[j+1][i+c[j]]);
        }
    }

    vector <int> bry(n+1,0);
    for(int i = 1; i <= n; i++) bry[i] = bry[i-1]+(s[i-1] == '_');

    string ans = s;
    for(int i = 0; i < n; i++){
        if(s[i] == '_'){
            ans[i] = '_';
            continue;
        }
        /// da li moze da bude X na i?
        bool mozex = 0;
        for(int j = 1; j <= k; j++){
            for(int poc = max(0,i-c[j]+1); poc <= i && poc+c[j]-1 < n; poc++){
                if(bry[poc+c[j]]-bry[poc] == 0 && pfdp[j-1][poc] && sfdp[j+1][poc+c[j]+1]) mozex = 1;
            }
        }
        /// da li moze da bude _ na i?
        bool mozey = 0;
        mozey |= (i <= n-(sum+k-1)-1 || i >= sum+k-1);
        for(int j = 1; j < k; j++){
            if(pfdp[j][i] && sfdp[j+1][i+2]) mozey = 1;
        }


        if(mozex && mozey) ans[i] = '?';
        else if(mozex) ans[i] = 'X';
        else if(mozey) ans[i] = '_';
    }

    return ans;
}

string solve_puzzle(string s1,vector <int> c1){
    n = s1.size();
    k = c1.size();
    s = s1;
    for(int i = 1; i <= k; i++) c[i] = c1[i-1];


    bool prz = 1,nemax = 1;
    for(auto f : s){
        if(f != '.') prz = 0;
        if(f == 'X') nemax = 0;
    }
    if(n <= 100 && prz){
        return prazna();
    }

    if(n <= 100 && nemax){
        return novo();
    }
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:150:1: warning: control reaches end of non-void function [-Wreturn-type]
  150 | }
      | ^

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10