Submission #591017

#	Time	Username	Problem	Language	Result	Execution time	Memory
591017		jasmin	Paint By Numbers (IOI16_paint)	C++14	32 / 100	1 ms	852 KiB

paint

#include<bits/stdc++.h>
#include<paint.h>
using namespace std;

void make_dp_front(string& s, vector<int>& c, vector<vector<vector<int> > >& dp){
    int n=s.size();
    int k=c.size();

    dp[0][0][0]=true;

    for(int i=1; i<=n; i++){
        for(int j=0; j<=k; j++){

            if(s[i-1]=='_'){//white
                dp[i][j][0]=dp[i-1][j][0] || dp[i-1][j][1];
                dp[i][j][1]=false;
            }
            else if(s[i-1]=='X'){ //black
                dp[i][j][0]=false;
                if(0<j && 0<=i-c[j-1]){
                    dp[i][j][1]=dp[i-c[j-1]][j-1][0];
                }
            }
            else{
                dp[i][j][0]=dp[i-1][j][0] || dp[i-1][j][1];
                if(0<j && 0<=i-c[j-1]){
                    dp[i][j][1]=dp[i-c[j-1]][j-1][0];
                }
            }
            
        }
    }
}
void make_dp_back(string& s, vector<int>& c, vector<vector<vector<int> > >& dp){
    int n=s.size();
    int k=c.size();

    dp[n][k][0]=true;

    for(int i=n-1; i>=0; i--){
        for(int j=k; j>=0; j--){

            if(s[i]=='_'){//white
                dp[i][j][0]=dp[i+1][j][0] || dp[i+1][j][1];
                dp[i][j][1]=false;
            }
            else if(s[i]=='X'){ //black
                dp[i][j][0]=false;
                if(j<k && i+c[j]<=n){
                    dp[i][j][1]=dp[i+c[j]][j+1][0];
                }
            }
            else{
                dp[i][j][0]=(dp[i+1][j][0] || dp[i+1][j][1]);
                if(j<k && i+c[j]<=n){
                    dp[i][j][1]=dp[i+c[j]][j+1][0];
                }
            }
            
        }
    }
}


string solve_puzzle(string s, vector<int> c){
    int n=s.size(); 
    int k=c.size();

    vector<vector<vector<int> > > dp_front(n+1, vector<vector<int> > (k+1, vector<int> (2, false)));
    make_dp_front(s, c, dp_front);
    vector<vector<vector<int> > > dp_back(n+1, vector<vector<int> > (k+1, vector<int> (2, false)));
    make_dp_back(s, c, dp_back);

    /*for(int i=0; i<n; i++){
        cout << i << ": \n";
        for(int j=0; j<k; j++){
            cout << "( " << dp_front[i+1][j+1][0] << ", " << dp_front[i+1][j+1][1] << ") ";
        }
        cout << "\n";
    }
    for(int i=0; i<n; i++){
        cout << i << ": \n";
        for(int j=0; j<k; j++){
            cout << "( " << dp_back[i][j][0] << ", " << dp_back[i][j][1] << ") ";
        }
        cout << "\n" << flush;
    }*/

    vector<bool> black(n);
    vector<bool> white(n);
    for(int j=0; j<k; j++){
        int r=1; //exklusiv
        int last=0;
        for(int l=0; l<n; l++){
            while(l<n && r<=n && r-l<c[j]){
                if(s[r]=='_'){
                    l=r+1;
                    r=r+1;
                }
                r++;
            }

            if(l==n || r>n) break;

            //cout << j << ": " << l << " " << r << "\n" << flush;
            if(r-l==c[j] && dp_front[l][j][0] && (r>n || dp_back[r][j+1][0])){
                //cout << "Yes " << last << "\n" << flush;
                last=max(last, l);
                for(int x=last; x<r; x++){
                    black[x]=true;
                    //cout << x << "true\n" << flush;
                }
                last=r;
            }
        }

    }
    for(int j=0; j<=k; j++){
        for(int i=0; i<n; i++){
            if((dp_front[i][j][0] || dp_front[i][j][1])
                && (dp_back[i+1][j][0] || dp_back[i+1][j][1])){

                    //cout << "ok white: " << i << "\n" << flush;
                    white[i]=true;
                }
        }
    }

    string ans=s;
    for(int i=0; i<n; i++){
        assert(black[i] || white[i]);
        if(s[i]=='_' || !black[i]){
            ans[i]='_';
        }
        else if(s[i]=='X' || !white[i]){
            ans[i]='X';
        }
        else{
            ans[i]='?';
        }
    }
    return ans;
}


/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> a(k);
    for(int i=0; i<k; i++){
        cin >> a[i];
    }

    string ans=solve_puzzle(s, a);
    cout << ans << "\n";
}*/

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