Submission #329839

#	Time	Username	Problem	Language	Result	Execution time	Memory
329839		wildturtle	Paint By Numbers (IOI16_paint)	C++14	100 / 100	608 ms	325716 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,pdp[200005][102],sdp[200005][102],A[200005],B[200005],C[200005];
string s1;
std::string solve_puzzle(std::string s, std::vector<int> c) {
    n=s.size(); m=c.size();
    c.insert(c.begin(),0);
    s='*'+s+'*';
    for(long long i=1;i<=n;i++) {
        A[i]=A[i-1];
        if(s[i]=='_') A[i]++;
    }
    for(long long i=0;i<=n+1;i++) {
        if(s[i]=='X') break;
        pdp[i][0]=1;
    }
    for(long long i=n+1;i>=0;i--) {
        if(s[i]=='X') break;
        sdp[i][m+1]=1;
    }
    for(long long i=1;i<=n;i++) {
        for(long long j=1;j<=m;j++) {
            if(s[i]!='X') pdp[i][j]=pdp[i-1][j];
            if(pdp[i][j]==1) continue;
            if(s[i]!='_' && i-c[j]+1>=1 && A[i]-A[i-c[j]]==0) {
                if(i-c[j]+1==1) { if(j==1)pdp[i][j]=1; }
                else if(s[i-c[j]]!='X') pdp[i][j]=pdp[i-c[j]-1][j-1];
            }
        }
    }
    for(long long i=n;i>=1;i--) {
        for(long long j=m;j>=1;j--) {
            if(s[i]!='X') sdp[i][j]=sdp[i+1][j];
            if(sdp[i][j]==1) continue;
            if(s[i]!='_' && i+c[j]-1<=n && A[i+c[j]-1]-A[i-1]==0) {
                if(i+c[j]-1==n) { if(j==m) sdp[i][j]=1; }
                else if(s[i+c[j]]!='X') sdp[i][j]=sdp[i+c[j]+1][j+1];
            }
        }
    }
    for(long long i=1;i<=n;i++) {
        if(s[i]=='X') continue;
        for(long long j=0;j<=m;j++) {
            //if(i==1) cout<<sdp[i+1][j+1]<<endl;
            if(pdp[i-1][j]==1 && sdp[i+1][j+1]==1) B[i]=1;
        }
    }
    for(long long i=1;i<=n;i++) {
        if(s[i]=='_') continue;
        for(long long j=1;j<=m;j++) {
            if(i-c[j]+1<=0) continue;
            if(i-c[j]+1>1 && s[i-c[j]]=='X') continue;
            a=0; b=0;
            if(i-c[j]-1<0) { if(j==1) a=1; }
            else if(s[i-c[j]]!='X') a=pdp[i-c[j]-1][j-1];
            if(i+2>n+1) { if(j==m) b=1; }
            else if(s[i+1]!='X') b=sdp[i+2][j+1];
            if(a==1 && b==1 && A[i]-A[i-c[j]]==0) { C[i+1]--; C[i-c[j]+1]++; }
        }
    }
    for(long long i=1;i<=n;i++) {
        C[i]+=C[i-1];
    }
    for(long long i=1;i<=n;i++) {
        if(B[i]==1 && C[i]!=0) s1+='?';
        else if(B[i]==1) s1+='_';
        else if(C[i]!=0) s1+='X';
    }
    return s1;
}/*
int main() {
    cout<<solve_puzzle(".X........", {3});
}*/

• 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