제출 #1232705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232705		dssfsuper2	Paint By Numbers (IOI16_paint)	C++20	80 / 100	0 ms	584 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
int dp[101][101];
string S, F;
vector<int> Lazy;
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(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){
            //cout << i << " cas1\n";
            Fv[i]|=1;
        }
        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){
            //cout << i << " cas2\n";
            Fv[i]|=2;
            Lazy[i]+=2;
            Lazy[min(n, i+C[j])]-=2;
            Fv[min(n, i+C[j])]|=1;
            //lazyxtheredo
        }
        if(!y)res=false;
    }
    else{
        
        bool x=dpf(i+1, j);
        if(x){
            Fv[i]|=1;
            //cout << i << " cas3\n";
        }
        bool y = false;
        if(!dsnc && isag){
            y = dpf(i+C[j]+1, j+1);
            if(y){
                //cout << i << " cas4\n";
                Fv[i]|=2;
                Lazy[i]+=2;
                Lazy[min(n, i+C[j])]-=2;
                Fv[min(n, i+C[j])]|=1;
                //lazyput there
            }
        }
        if(!x && !y)res=false;
    }
    //cout << i << ' ' << j << ' ' << (int)res << '\n';
    dp[i][j]=res;
    return res;
}

string solve_puzzle(string s, vector<int> c) {
    n=s.size();
    m=c.size();
    S=s;
    C=c;
    Fv.assign(n, 0);
    Lazy.assign(n+1, 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];
    }
    dpf(0, 0);
    int cl=0;
    for(int i = 0;i<n;i++){
        cl+=Lazy[i];
        if(cl)Fv[i]|=2;
    }
    // for(int j=0;j<5;j++){
    //     for(int i = 0;i<25;i++){
    //         cout << dp[i][j] << ' ' ;
    //     }
    //     cout << '\n';
    // }
    // cout << '\n';
    // for(auto thing:Fv){
    //     cout << thing<< ' ' ;
    // }
    // cout << '\n';
    string ss;
    for(int i = 0;i<n;i++){
        if(Fv[i]==1)ss.push_back('_');
        else if (Fv[i]==2)ss.push_back('X');
        else ss.push_back('?');
    }
    return ss;
}

컴파일 시 표준 에러 (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