Submission #1002398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002398		Malix	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	444 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<int,int,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

vii dp;
string s;
vi c;
int n,k;

int solve(int a,int b){
    if(dp[a][b]!=-1)return dp[a][b];
    REP(i,0,c[b]){
        if(a+i>=n)return dp[a][b]=0;
        if(s[a+i]=='_')return dp[a][b]=0;
    }
    if(a+c[b]<n&&s[a+c[b]]=='X')return dp[a][b]=0;
    if(b==k-1)return dp[a][b]=1;
    dp[a][b]=0;
    REP(i,a+c[b]+1,n){
        dp[a][b]|=solve(i,b+1);
        if(s[i]=='X')break;
    }
    return dp[a][b];
}

std::string solve_puzzle(std::string s1, std::vector<int> c1) {
    s=s1;
    c=c1;
    k=c.size();
    n=s.size();
    dp.resize(n,vi(k,-1));
    REP(i,0,n){
        solve(i,0);
        if(s[i]=='X')break;
    }
    string ans;
    ans.resize(n,'_');
    for(int i=k-1;i>=0;i--){
        vi p;
        REP(j,0,n)if(dp[j][i]>0)p.PB(j);
        if(p.empty())continue;
        REP(j,p.back(),p[0]+c[i])ans[j]='X';
        for(auto u:p){
            REP(j,u,u+c[i])if(ans[j]!='X')ans[j]='?';
        }
    }
    return ans;
}

• 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