Submission #1229712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229712		Malix	Paint By Numbers (IOI16_paint)	C++20	100 / 100	1491 ms	422956 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<ll,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n=s.size(),m=c.size();
    vii dp(m,vi(n,0)),dp2(m,vi(n,0));
    vi a(n,0),b;
    REP(i,0,n)if(s[i]=='_')a[i]=1;
    REP(i,0,n)if(s[i]=='X')b.PB(i);
    REP(i,1,n)a[i]+=a[i-1];
    for(int i=m-1;i>=0;i--){
        REP(j,0,n-c[i]+1){
            if(j!=0&&s[j-1]=='X')continue;
            if(j+c[i]<n&&s[j+c[i]]=='X')continue;
            if(a[j+c[i]-1]-(j==0?0:a[j-1])>0)continue;
            if(i!=m-1){
                int pos=lower_bound(all(b),j+c[i]+1)-b.begin();
                int mx=n-1;
                if(pos!=b.size())mx=b[pos];
                if(j+c[i]>=mx)continue;
                if(dp[i+1][mx]-dp[i+1][j+c[i]]==0)continue;
            }
            else if(b.size()&&b.back()>j+c[i]-1)continue;
            if(i==0&&b.size()&&b[0]<j)continue;
            
            dp[i][j]=1;
        }
        dp2[i]=dp[i];
        REP(j,1,n)dp[i][j]+=dp[i][j-1];
    }
    REP(j,1,n)dp2[0][j]+=dp2[0][j-1];
    REP(i,1,m){
        REP(j,0,n)if(dp2[i][j]){
            if((j-1-c[i-1]<0||dp2[i-1][j-1-c[i-1]]<=0))dp2[i][j]=0;
            int ps=lower_bound(all(b),j)-b.begin();
            ps--;
            if(ps>=0&&(j-c[i-1]-1<0||dp2[i-1][j-c[i-1]-1]-(b[ps]-c[i-1]<0?0:dp2[i-1][b[ps]-c[i-1]])<=0))dp2[i][j]=0;
        }
        REP(j,1,n)dp2[i][j]+=dp2[i][j-1];
    }
    dp=dp2;
    vi cnt(n,0);
    vector<pi> arr;
    REP(i,0,m)REP(j,0,n){
        if(i==0){
            if(dp[i][j]-(j==0?0:dp[i][j-1]))arr.PB({j,j+c[i]-1});
            continue;
        }
        if(dp[i][j]-(j==0?0:dp[i][j-1])>0&&j-1-c[i-1]>=0&&dp[i-1][j-1-c[i-1]])arr.PB({j,j+c[i]-1});
    }
    sort(all(arr));
    if(arr.size()){
        int l=arr[0].F,r=arr[0].S;
        REP(i,1,arr.size()){
            if(arr[i].F>r){
                REP(j,l,r+1)cnt[j]=1;
                l=arr[i].F;
                r=arr[i].S;
                continue;
            }
            r=max(r,arr[i].S);
        }
        REP(i,l,r+1)cnt[i]=1;
    }
    REP(j,0,n)if(s[j]=='.'){
        REP(i,0,m-1)if(j-c[i]>=0&&dp[i][j-c[i]]>0&&dp[i+1][n-1]-dp[i+1][j]>0){
            int ps=lower_bound(all(b),j)-b.begin();
            ps--;
            if(ps>=0&&(dp[i][j-c[i]]-(b[ps]-c[i]<0?0:dp[i][b[ps]-c[i]])<=0))continue;
            ps=lower_bound(all(b),j+1)-b.begin();
            if(ps!=b.size()&&dp[i+1][b[ps]]-dp[i+1][j]<=0)continue;
            cnt[j]+=2;
            break;
        }
        if(cnt[j]<=1&&(dp[0][n-1]-dp[0][j]>0||(j-c[m-1]>=0&&dp[m-1][j-c[m-1]]>0)))cnt[j]+=2;
    }
    string ans=s;
    REP(i,0,n)if(s[i]=='.'){
        if(cnt[i]==1)ans[i]='X';
        else if(cnt[i]==2)ans[i]='_';
        else if(cnt[i]==3)ans[i]='?';
    }
    return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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