Submission #773615

#	Time	Username	Problem	Language	Result	Execution time	Memory
773615		ttamx	Paint By Numbers (IOI16_paint)	C++14	80 / 100	3 ms	1748 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

typedef tuple<int,int,int> t3;

const int N=105;

bool dp[N][N][N],vis[N][N][N];

string solve_puzzle(string s, vector<int> c) {
    int n=s.size();
    int m=c.size();
    vector<int> v(n);
    dp[0][0][0]=true;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(s[i-1]=='_'||s[i-1]=='.'){
                dp[i][j][0]|=dp[i-1][j][0];
                if(j<m)dp[i][j+1][0]|=dp[i-1][j][c[j]];
            }
            if(s[i-1]=='X'||s[i-1]=='.'){
                for(int k=0;k<c[j];k++){
                    dp[i][j][k+1]|=dp[i-1][j][k];
                }
            }
        }
    }
    queue<t3> q;
    if(dp[n][m][0]){
        vis[n][m][0]=true;
        q.emplace(n,m,0);
    }
    if(dp[n][m-1][c[m-1]]){
        vis[n][m-1][c[m-1]]=true;
        q.emplace(n,m-1,c[m-1]);
    }
    while(!q.empty()){
        auto [i,j,k]=q.front();
        q.pop();
        if(i==0)continue;
        if(s[i-1]=='_'||s[i-1]=='.'){
            if(k==0&&dp[i-1][j][0]){
                v[i-1]|=2;
                if(!vis[i-1][j][0]){
                    vis[i-1][j][0]=true;
                    q.emplace(i-1,j,0);
                }
            }
            if(j>0&&k==0&&dp[i-1][j-1][c[j-1]]){
                v[i-1]|=2;
                if(!vis[i-1][j-1][c[j-1]]){
                    vis[i-1][j-1][c[j-1]]=true;
                    q.emplace(i-1,j-1,c[j-1]);
                }
            }
        }
        if(s[i-1]=='X'||s[i-1]=='.'){
            if(k>0&&dp[i-1][j][k-1]){
                v[i-1]|=1;
                if(!vis[i-1][j][k-1]){
                    vis[i-1][j][k-1]=true;
                    q.emplace(i-1,j,k-1);
                }
            }
        }
    }
    string ans="";
    for(auto x:v){
        if(x==1)ans+='X';
        if(x==2)ans+='_';
        if(x==3)ans+='?';
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         auto [i,j,k]=q.front();
      |              ^

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