Submission #781920

#	Time	Username	Problem	Language	Result	Execution time	Memory
781920		BT21tata	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	468 KiB

paint

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

bool dp[200005][205];
int n, prx[200005], k, pre[200005], canx[200005], cane[200005];
set<int>pos[205];
string ans;

string solve_puzzle(string s, vector<int> c)
{
    n=s.length();
    k=c.size();
    for(int i=0; i<n; i++)
    {
        if(s[i]=='X') prx[i]=1;
        if(s[i]=='_') pre[i]=1;
        if(i) prx[i]+=prx[i-1], pre[i]+=pre[i-1];
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<k; j++)
        {
            if((j and pos[j-1].size()==0) or i-c[j]+1<0) continue;
            if(!j)
            {
                if(pre[i]-pre[i-c[j]]==0 and prx[i-c[j]]==0 and s[i+1]!='X')
                {
                    dp[i][j]=1;
                    pos[j].insert(i);
                }
                continue;
            }
            auto it=pos[j-1].upper_bound(i-c[j]-1);
            if(it==pos[j-1].begin()) continue;
            --it;
            if(pre[i]-pre[i-c[j]]==0 and prx[i-c[j]]-prx[*it]==0 and s[i+1]!='X')
            {
                if(j==k-1 and prx[n-1]-prx[i]) continue;
                dp[i][j]=1;
                pos[j].insert(i);
            }
        }
    }
    
    int last=n-1;
    /*for(int i=0; i<k; i++)
    {
        cout<<"pos["<<i<<"] = ";
        for(int u : pos[i])
            cout<<u<<' ';
        cout<<endl;
    }*/
    for(int j=k-1; j>=0; j--)
    {
        auto it=pos[j].begin();
        cane[(*it)+1]++;
        cane[last+2]--;
        // cout<<"in cane : "<<(*it)+1<<' '<<last<<endl;
        auto it2=pos[j].upper_bound(last);
        --it2;
        last=((*it2)-c[j]-1);
        for(; ; --it2)
        {
            // (*it2)-c[j]+1 ... (*it2)
            if(j!=k-1)
            {
                auto itplu=pos[j+1].lower_bound(*(it2)+1+c[j+1]);
                if(prx[(*itplu)-c[j+1]]-prx[*it2])
                {
                    if(it2==pos[j].begin()) break;
                    else continue;
                }
            }
            canx[(*it2)-c[j]+1]++;
            canx[(*it2)+1]--;
            // cout<<"in canx : "<<j<<' '<<(*it2)-c[j]+1<<' '<<(*it2)<<endl;
            if(it2==pos[j].begin()) break;
        }
        // cout<<"last "<<last<<endl;
    }
    if(last+2>=0) cane[0]++, cane[last+2]--;
    for(int i=1; i<n; i++)
        cane[i]+=cane[i-1], canx[i]+=canx[i-1];
    for(int i=0; i<n; i++)
    {
        // cout<<i<<' '<<canx[i]<<' '<<cane[i]<<endl;
        if(s[i]=='.')
        {
            if(cane[i] and canx[i]) ans+='?';
            else if(cane[i]) ans+='_';
            else ans+='X';
        }
        else ans+=s[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