Submission #757123

#	Time	Username	Problem	Language	Result	Execution time	Memory
757123		Khizri	Paint By Numbers (IOI16_paint)	C++17	100 / 100	775 ms	169268 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
int n,k,arr[mxn],pre[mxn],bla[mxn],pos[mxn][105],pos2[mxn][105],l[mxn],r[mxn];
vector<int>vt;
string s;
int check(int l){
    if((pos[l-1][k]&&bla[n]-bla[l]==0)||(pos2[l+1][1]&&bla[l-1]==0)) return 1;
    for(int i=1;i<=k-1;i++){
        if(pos[l-1][i]&&pos2[l+1][i+1]) return 1;
    }
    return 0;
}
void check2(int l){
    for(int i=1;i<=k;i++){
        if(l+arr[i]>n+1) continue;
        if(s[l-1]=='X'||s[l+arr[i]]=='X') continue;
        int x=l,y=l+arr[i]-1;
        if(pre[y]-pre[x-1]==0){
            if(pos[max(0,l-2)][i-1]&&pos2[min(n+1,y+2)][i+1]){
                r[x]++;
                r[y+1]--;
            }
        }
    }
}
string solve_puzzle(string S, vector<int> c) {
    for(int i=0;i<c.size();i++){
        arr[i+1]=c[i];
    }
    s=".";
    s+=S;
    s+='.';
    n=S.size();
    k=c.size();
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1];
        bla[i]=bla[i-1];
        if(s[i]=='_') pre[i]++;
        if(s[i]=='X') bla[i]++;
    }
    for(int i=1;i<=n;i++){
        if(bla[i]==0){
            pos[i][0]=1;
        }
        else{
            pos[i][0]=0;
        }
    }
    pos[0][0]=1;
    int sum=0;
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++){
            if(j<arr[i]){
                pos[j][i]=0;
                continue;
            }
            if(s[j]!='X'){
                pos[j][i]=pos[j-1][i];
            }
            if(s[j]!='_'&&pre[j]-pre[j-arr[i]]==0&&(j-arr[i]<=0||s[j-arr[i]]!='X')){
                pos[j][i]=max(pos[j][i],pos[max(0,j-arr[i]-1)][i-1]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(bla[n]-bla[i-1]==0){
            pos2[i][k+1]=1;
        }
        else{
            pos2[i][k+1]=0;
        }
    }
    pos2[n+1][k+1]=1;
    for(int i=k;i>=1;i--){
        for(int j=n;j>=1;j--){
            if(j+arr[i]-1>n){
                pos2[j][i]=0;
                continue;
            }
            if(s[j]!='X'){
                pos2[j][i]=pos2[j+1][i];
            }
            if(s[j]!='_'&&pre[j+arr[i]-1]-pre[j-1]==0&&(s[j+arr[i]]!='X'||j+arr[i]==n+1)){
                pos2[j][i]=max(pos2[j][i],pos2[min(n+1,j+arr[i]+1)][i+1]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(s[i]=='.'){
            l[i]=check(i);
        }
        else{
            l[i]=0;
        }
        check2(i);
    }
    for(int i=1;i<=n;i++){
        r[i]+=r[i-1];
    }
    /*
    for(int i=1;i<=n;i++){
        cout<<l[i]<<' ';
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        cout<<r[i]<<' ';
    }
    cout<<endl;
    */
    string ans="";
    for(int i=1;i<=n;i++){
        if(s[i]!='.'){
            ans+=s[i];
            continue;
        }
        if(l[i]&&r[i]>0){
            ans+='?';
        }
        else if(l[i]){
            ans+='_';
        }
        else{
            ans+='X';
        }
    }
    return ans;
}
/*
X......
1 5
*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<c.size();i++){
      |                 ~^~~~~~~~~
paint.cpp:64:9: warning: unused variable 'sum' [-Wunused-variable]
   64 |     int sum=0;
      |         ^~~

• 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