Submission #532417

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

paint

#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "paint.h"
using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

int pr1[2*maxn], pr2[2*maxn],pr3[2*maxn][101];
bool dp1[2*maxn][101], dp2[2*maxn][101],no[2*maxn],yes[2*maxn];
string solve_puzzle(string s,vector<int> c){

    int n = sz(s), k = sz(c);
    c.insert(begin(c),0);
    for(int i=0;i<n;++i){
        pr1[i+1] = pr1[i], pr2[i+1] = pr2[i];
        pr1[i+1] += s[i]=='_', pr2[i+1] += s[i]=='X';
    }
    dp1[0][0] = dp2[0][0] = 1;
    for(int j=0;j<=k;++j){
        for(int i=1;i<=n;++i){
            if(j==0){
                dp1[i][j] = pr2[i]==0;
            }else{
                if(s[i-1]=='_'){
                    dp1[i][j] = dp1[i-1][j];
                }else if(s[i-1]=='X'){
                    if(c[j]>i)dp1[i][j] = 0;
                    else if(c[j]==i)dp1[i][j] = (pr1[i]==0&&j==1);
                    else dp1[i][j] = (!(pr1[i]-pr1[i-c[j]])&&s[i-c[j]-1]!='X'&&dp1[i-c[j]-1][j-1]);
                }else{
                    dp1[i][j] = dp1[i-1][j];
                    if(c[j]>i)dp1[i][j] |= 0;
                    else if(c[j]==i)dp1[i][j] |= (pr1[i]==0&&j==1);
                    else dp1[i][j] |= (!(pr1[i]-pr1[i-c[j]])&&s[i-c[j]-1]!='X'&&dp1[i-c[j]-1][j-1]);
                }
            }
        }
    }
    for(int j=0;j<=k;++j){
        for(int i=1;i<=n;++i){
            int revi = n - i + 1, revj = k - j + 1;
            if(j==0)dp2[i][j] = (pr2[n] - pr2[revi-1]==0);
            else{
                if(s[revi-1]=='_')dp2[i][j] = dp2[i-1][j];
                if(s[revi-1]=='X'){
                    if(c[revj]>i)dp2[i][j] = 0;
                    else if(c[revj]==i)dp2[i][j] = (pr1[n]-pr1[revi-1]==0&&j==1);
                    else dp2[i][j]=(pr1[revi+c[revj]-1]-pr1[revi-1]==0&&
                    s[revi+c[revj]]!='X'&&dp2[i-c[revj]-1][j-1]);
                }else{
                    dp2[i][j] = dp2[i-1][j];
                    if(c[revj]>i)dp2[i][j] |= 0;
                    else if(c[revj]==i)dp2[i][j] |= (pr1[n]-pr1[revi-1]==0&&j==1);
                    else dp2[i][j]|=(pr1[revi+c[revj]-1]-pr1[revi-1]==0&&
                    s[revi+c[revj]]!='X'&&dp2[i-c[revj]-1][j-1]);
                }
            }
        }
    }
    // for(int j=0;j<=k;++j){
    //     for(int i=1;i<=n;++i){
    //         cout<<dp1[i][j]<<" \n"[i==n];
    //     }
    // }
    // for(int j=0;j<=k;++j){
    //     for(int i=1;i<=n;++i){
    //         cout<<dp2[i][j]<<" \n"[i==n];
    //     }
    // }
    for(int i=1;i<=n;++i)
        for(int j=0;j<=k;++j)
            no[i]|=dp1[i-1][j]&&dp2[n-i][k-j]&&s[i-1]!='X';
    // for(int i=1;i<=n;++i)cout<<no[i]<<" \n"[i==n];
    for(int j=1;j<=k;++j){  
        for(int i=c[j];i<=n;++i){
            pr3[i][j] = pr3[i-1][j];
            if(j==1||j==k){
                if((j!=1?i>c[j]&&dp1[i-c[j]-1][j-1]:dp1[i-c[j]][j-1])
                &&(i!=c[j]?s[i-c[j]-1]!='X':1)&&(j!=k?i!=n&&dp2[n-i-1][k-j]:
                dp2[n-i][k-j])&&
                (i!=n?s[i]!='X':1)&&pr1[i]-pr1[i-c[j]]==0)pr3[i][j]++;
            }else{
                if(i==c[j]||i==n)continue;
                if(dp1[i-c[j]-1][j-1]&&s[i-c[j]-1]!='X'
                &&dp2[n-i-1][k-j]&&s[i]!='X'&&pr1[i]-pr1[i-c[j]]==0)pr3[i][j]++;
            }
            }
        }
    
    for(int i=1;i<=n;++i){
        for(int j=1;j<=k;++j){
            yes[i]|=(pr3[min(n,i+c[j]-1)][j]-pr3[i-1][j]);
        }
    }
    // for(int j=1;j<=k;++j){
    //     for(int i=1;i<=n;++i)
    //         cout<<pr3[i][j]<<" \n"[i==n];
    // }
    // for(int i=1;i<=n;++i)cout<<yes[i]<<" "<<no[i]<<endl;
    for(int i=0;i<n;++i){
        if(s[i]=='.'){
            if(yes[i+1]&&no[i+1])s[i]='?';
            else if(yes[i+1])s[i]='X';
            else s[i]='_';
        }
    }
    return s;
}


// int main(){
    // string s;int k;cin>>s>>k;
    // vector<int>c(k);
    // for(auto& x:c)cin>>x;
    // cout<<solve_puzzle(s,c);
// }

• 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