Submission #209572

#	Time	Username	Problem	Language	Result	Execution time	Memory
209572		DavidDamian	Paint By Numbers (IOI16_paint)	C++11	59 / 100	6 ms	380 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
struct range
{
    int L,R;
};
int available[200005];
string solve_puzzle(string s, vector<int> c) {
    int k=c.size();
    int n=s.size();
    string ans=s;
    int actID=0;
    vector<range> ranges(k+1);
    if(s[n-1]=='.') available[n-1]=1;
    for(int i=n-2;i>=0;i--){
        if(s[i]=='.') available[i]=available[i+1]+1;
        else available[i]=0;
    }
    for(int i=0;i<k;i++){
        while(available[actID]<c[i]) actID++;
        ranges[i].L=actID;
        actID+=(c[i]+1);
    }
    if(s[0]=='.') available[0]=1;
    else available[0]=0;
    for(int i=1;i<n;i++){
        if(s[i]=='.') available[i]=available[i-1]+1;
        else available[i]=0;
    }
    actID=n-1;
    for(int i=k-1;i>=0;i--){
        while(available[actID]<c[i]) actID--;
        ranges[i].R=actID;
        actID-=c[i]+1;
    }
    for(int i=0;i<k;i++){
        int m=ranges[i].R-ranges[i].L+1;
        for(int j=0;j<m;j++){
            int id=j+ranges[i].L;
            if(j>m-c[i]-1 && j<c[i]) ans[id]='X';
            else ans[id]='?';
        }
    }
    for(int i=0;i<n;i++){
        if(ans[i]=='.' || s[i]=='_') ans[i]='_';
    }
    return ans;
}

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