제출 #1245105

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

paint

#include "paint.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
vector <int> comb(vector <vector <int> > aux, string fr){
    int n=aux.size();
    int m=aux[0].size();
    for(int i=0; i<m; ++i){
        if(fr[i]!='?'){
            int nose=aux[0][i];
            for(int j=1; j<n; ++j){
                if(nose!=aux[j][i]){
                    nose=2;
                    break;
                }
            }
            if(nose==1 && fr[i]=='_'){
                nose=2;
            }
            if(nose==0 && fr[i]=='X'){
                nose=2;
            }
            if(nose==2){
                fr[i]='?';
            }
            else if(nose==1){
                fr[i]='X';
            }
            else{
                fr[i]='_';
            }
        }
    }
    vector <int> ans;
    ans.resize(m);
    for(int i=0; i<m; ++i){
        if(fr[i]=='?'){
            ans[i]=2;
        }
        else if(fr[i]=='X'){
            ans[i]=1;
        }
        else if(fr[i]=='_'){
            ans[i]=0;
        }
    }
    return ans;
}
string solve_puzzle(string s, vector <int> c){
    string fr="";
    int n=s.length();
    for(int i=0; i<n; ++i){
        fr+='.';
    }
    s+="_";
    int k=c.size();
    ++n;
    vector < vector <pair <int, vector <int> > > > DP;
    vector <int> ps;
    ps.resize(n+1);
    ps[n-1]=k;
    ps[n]=k;
    for(int i=n-2; i>=0; --i){
        if(ps[i+1]>0){
            int xd=ps[i+1];
            for(int j=c[xd-1]; j>=0; --j){
                ps[i]=xd-1;
                --i;
            }
            ++i;
        }
        else{
            ps[i]=0;
        }
    }
    DP.resize(n);
    if(s[0]!='_'){
        bool me=1;
        for(int i=0; i<c[0]; ++i){
            if(s[i]=='_'){
                me=0;
                break;
            }
        }
        if(me){
            if(s[c[0]]!='X'){
                vector <int> aux;
                aux.assign(c[0], 1);
                aux.pb(0);
                DP[c[0]].pb({1, aux});
            }
        }
    }
    if(s[0]!='X'){
        DP[0].pb({0, {0}});
    }
    for(int i=1; i<n; ++i){
        sort(DP[i-1].begin(), DP[i-1].end());
        int us=0;
        vector <pair <int, vector <int> > > nah;
        for(int j=0; j<DP[i-1].size(); j=us+1){
            us=j;
            if(us<DP[i-1].size()-2){
                int tdems=DP[i-1].size();
                while(DP[i-1][us].fi==DP[i-1][us+1].fi && us<tdems-2){
                    ++us;
                }
            }
            if(us==DP[i-1].size()-2){
                if(DP[i-1][us].fi==DP[i-1][us+1].fi){
                    ++us;
                }
            }
            vector <vector <int> > aux;
            aux.resize(0);
            for(int l=j; l<=us; ++l){
                aux.pb(DP[i-1][l].se);
            }
            DP[i-1][j].se=comb(aux, fr);
            nah.pb(DP[i-1][j]);
        }
        DP[i-1].resize(nah.size());
        for(int j=0; j<nah.size(); ++j){\
            DP[i-1][j]=nah[j];
        }
        for(int j=0; j<DP[i-1].size(); ++j){
            bool nose=1;
            vector <int> aux=DP[i-1][j].se;
            if(DP[i-1][j].fi==k){
                for(int l=i; l<n; ++l){
                    if(s[l]=='X'){
                        nose=0;
                        break;
                    }
                }
                if(nose){
                    for(int l=i; l<n; ++l){
                        aux.pb(1);
                    }
                    DP[n-1].pb({k, aux});
                }
            }
            else{
                for(int l=0; l<c[DP[i-1][j].fi]; ++l){
                    if(s[l+i]=='_'){
                        nose=0;
                    }
                }
                if(nose){
                    if(s[i+c[DP[i-1][j].fi]-1]!='X'){
                        for(int l=0; l<c[DP[i-1][j].fi]; ++l){
                            aux.pb(1);
                        }
                        aux.pb(0);
                        DP[i+c[DP[i-1][j].fi]-1].pb({DP[i-1][j].fi+1, aux});
                    }
                }
                if(s[i]!='X' && ps[i+1]<=DP[i-1][j].fi){
                    DP[i].pb(DP[i-1][j]);
                    DP[i][DP[i].size()-1].se.pb(0);
                }
            }
        }
        DP[i-1].resize(0);
    }
    --n;
    vector <vector <int> > TDP;
    for(int i=0; i<DP[n].size(); ++i){
        if(DP[n][i].fi==k){
            TDP.pb(DP[n][i].se);
        }
    }
    if(TDP.size()==0){
        return fr;
    }
    for(int j=0; j<n; ++j){
        if(fr[j]!='?'){
            int as=TDP[0][j];
            for(int i=0; i<TDP.size(); ++i){
                if(as!=TDP[i][j] || as==2){
                    fr[j]='?';
                    break;
                }
                if(i==TDP.size()-1){
                    if(TDP[i][j]==0){
                        fr[j]='_';
                        break;
                    }
                    fr[j]='X';
                    break;
                }
            }
        }
    }
    return fr;
}

컴파일 시 표준 에러 (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: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10