Submission #598488

#	Time	Username	Problem	Language	Result	Execution time	Memory
598488		chirathnirodha	Paint By Numbers (IOI16_paint)	C++17	0 / 100	0 ms	212 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#include <cstdlib>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first 
#define S second
#define P push
#define I insert 

string solve_puzzle(string s, vector<int> c) {
    int n=s.size(),k=c.size();
    bool dp[n][k];memset(dp,false,sizeof(dp));

    int lb[n],lw[n];
    int cb=-1,cw=-1;
    for(int i=0;i<n;i++){
        lb[i]=cb;lw[i]=cw;
        if(s[i]=='X')cb=i;
        if(s[i]=='_')cw=i;
    }
    vector<int> val[k];
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            if(s[i]=='_' || i-c[j]<-1)continue;

            if(i-c[j]==-1){
                if(lw[i]<=i-c[j] && j==0){
                    dp[i][j]=true;
                    val[j].PB(i);
                }
                continue;
            }
            if(lw[i]>i-c[j])continue;
            int lastbl=lb[i-c[j]+1];
            if(j==0 && lastbl!=-1)continue;
            if(j>0){
                auto low=lower_bound(val[j-1].begin(),val[j-1].end(),lastbl);
                if(low==val[j-1].end() || *low>=i-c[j])continue;
            }
            dp[i][j]=true;
            val[j].PB(i);
        }
    }
    queue<pair<int,int> > q;
    for(int i=0;i<val[k-1].size();i++){
        if(val[k-1][i]>cb)break;
        q.P(MP(val[k-1][i],k-1));
    }
    set<int> bl,wh;
    for(int i=0;i<n;i++){
        if(s[i]=='.'){
            bl.I(i);
            wh.I(i);
        }
    }
    bool canbl[n],canwh[n];
    memset(canbl,false,sizeof(canbl));memset(canwh,false,sizeof(canwh));
    while(!q.empty()){
        pair<int,int> p=q.front();q.pop();
        if(p.S==0)continue;
        int l=p.F-c[p.S]+1;int r=p.F;
        //Mark Black
        auto bx=lower_bound(bl.begin(),bl.end(),l);
        auto by=lower_bound(bl.begin(),bl.end(),r);
        auto x=bx;
        while(true){
            if(x==bl.end())break;
            canbl[*x]=true;
            if(x==by)break;
            x++;
        }
        if(bx!=bl.end())bl.erase(bx,by);
        //Mark White
        auto wx=upper_bound(wh.begin(),wh.end(),lb[l]);
        auto wy=lower_bound(wh.begin(),wh.end(),l-1);
        auto y=wx;
        while(true){
            if(y==wh.end())break;
            canwh[*y]=true;
            if(y==wy)break;
            y++;
        }
        if(wx!=wh.end())wh.erase(wx,wy);
        //Find next
        auto px=lower_bound(val[p.S-1].begin(),val[p.S-1].end(),lb[l]);
        auto py=lower_bound(val[p.S-1].begin(),val[p.S-1].end(),l-2);
        auto z=px;
        while(true){
            if(z==val[p.S-1].end())break;
            q.P(MP(*z,p.S-1));
            if(z==py)break;
            z++;
        }
        if(px!=val[p.S-1].end())val[p.S-1].erase(px,py);
    }
    for(int i=0;i<n;i++){
        if(s[i]=='.'){
            if(canbl[i] && canwh[i])s[i]='?';
            else if(canbl[i])s[i]='X';
            else s[i]='_';
        }
    }
    return s;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<val[k-1].size();i++){
      |                 ~^~~~~~~~~~~~~~~~

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