Submission #1021815

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

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

int a[200100];
int pref[200100], suf[200100];
int ok[200100][2];
int c[200100];


string solve_puzzle(string s, vector<int> C) {
    int k = C.size();
    int n = s.size();
    for(int i=0; i<k; i++){
        c[i+1] = C[i];
    }
    for(int i=1; i<=k; i++){
        pref[i] = c[i] + pref[i - 1];
    }
    for(int i=k; i>=1; i--){
        suf[i] = suf[i + 1] + c[i];
    }
    for(int i=0; i<n; i++){
        if(s[i] == 88) a[i + 1] = 1;
        if(s[i] == 95) a[i + 1] = 2;
        if(s[i] == 46) a[i + 1] = 0;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            int l=max(1, i-c[j] + 1);
            int r=min(n-c[j]+1, i);
            for(int h=l; h<=r; h++){
                if(pref[j-1]+j-1 <= h-1 and suf[j + 1] + k-j <= n-(h+c[j]-1)){
                    ok[i][1] = 1;
                    //if(i==4) cout<<j<<' '<<h<<'\n';
                }
            }
            //if(i == 4) cout<<pref[j]<<' '<<j-1<<' '<<suf[j+1]<<' '<<k-j-1<<' '<<n-i<<'\n';
            if(pref[j] + j-1 <= i - 1 and suf[j + 1] + k-j-1 <= n - i) ok[i][0] = 1;
            if(pref[j-1] + j-2 <= i - 1 and suf[j] + k-j <= n - i) ok[i][0] = 1;
        }
    }
    //cout<<ok[4][0]<<ok[4][1]<<'\n';
    
    string ans;
    for(int i=1; i<=n; i++){
        char c;
        if(ok[i][1] and ok[i][0]) c = '?';
        else if(ok[i][1]) c = 'X';
        else c = '_';
        ans.pb(c);
    }
            

    
    return ans; 
}

• 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