Submission #1232144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232144		dssfsuper2	Paint By Numbers (IOI16_paint)	C++20	80 / 100	143 ms	528 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
int dp[101][101];
string S, F;

vector<int> C, Fv;
vector<vector<int>> prs(3, vector<int>(104, 0));
int n, m;
//ispossible dp
int prf(int i, int j, char c){
    int x;
    j = min(j, n-1);
    if(c=='.')x=0;
    if(c=='X')x=1;
    if(c=='_')x=2;
    return prs[x][j+1]-prs[x][i];
}
bool dpf(int i, int j){
    
    bool res=true;
    if(j==m && (i==n || i==n+1))return true;
    if(i==n && j<m)return false;
    if(j>m)return false;
    if(i>n)return false;
    if(j==m && prf(i, n, 'X')>0)return false;
    if(j==m && prf(i, n, 'X')==0)return true;
    if(dp[i][j]!=2)return (bool)dp[i][j];
    int dsnc = prf(i, i+C[j]-1, '_');
    int xsnc = prf(i, i+C[j]-1, 'X');
    bool isag = (i+C[j]>=n || S[i+C[j]]=='.' || S[i+C[j]]=='_');
    //cout << i << ' ' << j << ' ' << (int)isag << ' ' << S << '\n';
    //cout << i << ' ' << j << ' ' <<dsnc << ' ' << dsnc2 << ' ' << xsnc << ' ' << S << '\n';
    if(dsnc){
        //am forced to be blank
        if(S[i]=='X'){
            res=false;
            dp[i][j]=res;
            return res;
        }
        bool x=dpf(i+1, j);
        if(!x)res=false;
    }
    else if (S[i]=='X'){
        if(dsnc || !isag){
            res= false;
            dp[i][j]=res;
            return res;
        }
        bool y = dpf(i+C[j]+1, j+1);
        if(!y)res=false;
    }
    else{
        
        bool x=dpf(i+1, j);
        bool y = false;
        if(!dsnc && isag)y = dpf(i+C[j]+1, j+1);
        if(!x && !y)res=false;
    }
    //cout << i << ' ' << j << ' ' << (int)res << '\n';
    dp[i][j]=res;
    return res;
}
bool solvable(string s, vector<int> c){
    n=s.size();
    m=c.size();
    S=s;
    C=c;
    Fv.assign(n, 0);
    vector<int> vals(3, 0);
    prs[0][0]=0;
    prs[1][0]=0;
    prs[2][0]=0;
    int i = 0;
    for(int i = 0;i<101;i++)for(int j = 0;j<101;j++)dp[i][j]=2;
    for(auto thing:s){
        if(s[i]=='.')vals[0]++;
        if(s[i]=='X')vals[1]++;
        if(s[i]=='_')vals[2]++;
        i+=1;
        prs[0][i]=vals[0];
        prs[1][i]=vals[1];
        prs[2][i]=vals[2];
    }
    for(int i = n;i<=103;i++){
        prs[0][i]=vals[0];
        prs[1][i]=vals[1];
        prs[2][i]=vals[2];
    }
    return dpf(0, 0);
}
string solve_puzzle(string s, vector<int> c) {
   string res;
   n=s.size();
   for(int i = 0;i<n;i++){
    if(s[i]!='.'){
        res.push_back(s[i]);
        continue;
    }
    //cout << i << '\n';
    s[i]='X';
    int t = 0;
    if (solvable(s, c))t|=1;
    s[i]='_';
    if (solvable(s, c))t|=2;
    if(t==1)res.push_back('X');
    else if (t==2)res.push_back('_');
    else if (t==3) res.push_back('?');
    s[i]='.';
    //cout << res << '\n';
   }
   
   return res;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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