Submission #412844

#	Time	Username	Problem	Language	Result	Execution time	Memory
412844		losmi247	Paint By Numbers (IOI16_paint)	C++14	32 / 100	1 ms	308 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++){
                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;
}

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];

    if(n <= 100){
        return prazna();
    }
}

Compilation message (stderr)

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

• 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