제출 #291236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
291236		REALITYNB	Paint By Numbers (IOI16_paint)	C++14	32 / 100	9 ms	5888 KiB

paint

#include <bits/stdc++.h> 
using namespace std;
vector<int> b , w ;  
vector<int> c; 
string a ; 
vector<int> p ; 
int n , k ; 
vector<vector<vector<int>>> mem(1e3,vector<vector<int>>(100,vector<int>(2,-1))) ; 
bool theresno(int i , int j){
    int minus = 0;  
    if(i) minus=p[i-1 ] ; 
    return p[j]==minus ; 
}
bool dp(int i , int j , int color){
    if(i==n&&j==k) return 1 ; 
    if(i>=n) return 0 ;
    if(color&&a[i]=='X') return 0 ;
    if(color==0&&a[i]==(char)(95)) return 0 ; 
    if(mem[i][j][(int)color]!=-1) return mem[i][j][color]; 
    //if(i==3&&color) cout << 1 << " " ; 
    bool ok =1;//dp(i+1,j) ; 
   // if(i==2&&color==1) cout << i << " ";
    if(j==k){
        ok=dp(i+1,j,1) ; 
        if(ok)w[i]++ ; 
    }
    else{
        if(color){
            ok = dp(i+1,j,0)|dp(i+1,j,1) ; 
            if(ok) w[i]++; 
        }
        else{
            ok = dp(i+c[j],j+1,1); 
            if(ok) ok&=theresno(i,i+c[j]-1) ;
            if(ok) b[i]++; 
            if(ok&&i+c[j]<=n)b[i+c[j]]--  ; 
        }
    }

    mem[i][j][color]=ok ; 
    return ok ; 
}
string solve_puzzle(string bb , vector<int> cc){
    //int n , k ; 
    a = bb ; 
    c = cc ;
    n = a.size() ; 
    k = c.size() ; 
  //  cout << n <<" "<< k <<endl ; 
    b.resize(n+1); 
    w.resize(n+1) ;
    p.resize(n+1) ; 
    for(int i=0;i<n;i++){
        if(i) p[i]+=p[i-1] ; 
        p[i]+=(a[i]==(char)(95)); 
    }
    dp(0,0,0) ; 
    dp(0,0,1) ;   
    vector<char> ans(n,(char)(95)) ;
    for(int i=0;i<n;i++){
        if(i) b[i]+=b[i-1] ; 
//        cout << b[i] << " " << w[i] << endl ; 
        if(b[i]&&w[i]) ans[i]='?' ; 
        else if(b[i]) ans[i]='X' ; 
    }
    string rans ; 
    for(char x : ans)rans+=x ; 
    return rans ; 

}

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