Submission #598648

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

paint

#include "paint.h"
#include<bits/stdc++.h>
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);
        }
    }
    set<int> bl,wh;
    bool visited[n][k];memset(visited,false,sizeof(visited));
    bool canbl[n],canwh[n];
    memset(canbl,false,sizeof(canbl));memset(canwh,false,sizeof(canwh));
    for(int i=0;i<n;i++){
        if(s[i]=='.'){
            bl.I(i);
            wh.I(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));
    }
    
    if(!q.empty())for(int i=q.front().F+1;i<n;i++)canwh[i]=true;
    
    while(!q.empty()){
        pair<int,int> p=q.front();q.pop();
        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+1);
        if(by==bl.begin())bx=bl.end();
        else{
            by--;
            if(*by<*bx)bx=bl.end();
        }
        auto x=bx;
        while(true){
            if(x==bl.end())break;
            canbl[*x]=true;
            if(x==by)break;
            x++;
        }
        if(by!=bl.end())by++;
        if(bx!=bl.end())bl.erase(bx,by);
        if(p.S==0){
            if(wh.empty())continue;
            auto itr=wh.begin();
            for(itr;itr!=wh.end();itr++){
                if(*itr>=l)break;
                canwh[*itr]=true;
            }
            wh.erase(wh.begin(),itr);
            continue;
        }
        //Mark White
        auto px=lower_bound(val[p.S-1].begin(),val[p.S-1].end(),lb[l]);
        auto wx=upper_bound(wh.begin(),wh.end(),max(lb[l],*px));
        auto wy=lower_bound(wh.begin(),wh.end(),l);
        if(wy==wh.begin())wx=wh.end();
        else{
            wy--;
            if(*wy<*wx)wx=wh.end();
        } 
        auto y=wx;
        while(true){
            if(y==wh.end())break;
            canwh[*y]=true;
            if(y==wy)break;
            y++;
        }
        if(wy!=wh.end())wy++;
        if(wx!=wh.end())wh.erase(wx,wy);
        //Find next
        
        auto py=lower_bound(val[p.S-1].begin(),val[p.S-1].end(),l-1);
        if(py==val[p.S-1].begin())px=val[p.S-1].end();
        else{
            py--;
            if(*py<*px)px=val[p.S-1].end();
        }
        auto z=px;
        while(true){
            if(z==val[p.S-1].end())break;
            if(visited[*z][p.S-1]==false){
                q.P(MP(*z,p.S-1));
                visited[*z][p.S-1]=true;
            }
            if(z==py)break;
            z++;
        }
    }
    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:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<val[k-1].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
paint.cpp:86:17: warning: statement has no effect [-Wunused-value]
   86 |             for(itr;itr!=wh.end();itr++){
      |                 ^~~

• 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