제출 #1192295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192295		meisgood	Paint By Numbers (IOI16_paint)	C++20	100 / 100	361 ms	54460 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std ;
#include <cstdlib>
bool dp[200003][103] ;
bool can[200003][103] ;
int n,k ;
string s ;
vector <int> c ;
int psw[200003],psb[200003] ;
// vector <int> adj[200003][103] ;
int www[200003],bbb[200003] ;
void dfs(int x,int y){
    if (x==n+1&&y==k){
        can[x][y]=1 ;
        return ;
    }
    if (y>k) return ;
    if (dp[x][y]) return ;
    dp[x][y]=1 ;
    // cout << x << " " << y << endl ;
    if (x<=n){
        if ((x+1>n||s[x+1]!='X')&&s[x]!='X'){
            dfs(x+1,y) ;
            if (can[x+1][y]){
                can[x][y]=1 ;
                www[x]++ ;
                www[x+1]-- ;
            }
            // lst[x+1][y]={x,y} ;
            // adj[x+1][y].push_back({x*101+y}) ;
        }
    }
    if (x+c[y]<=n){
        if (psw[x+c[y]]-psw[x]==0&&(x+c[y]==n||s[x+c[y]+1]!='X')){
            dfs(x+c[y]+1,y+1) ;
            if (can[x+c[y]+1][y+1]){
                can[x][y]=1 ;
                int a=x+c[y]+1 ;
                int b=y+1 ;
                bbb[x+1]++ ;
                bbb[a]-- ;
                www[x]++ ;
                www[x+1]-- ;
                www[a]++ ;
                www[a+1]-- ;
            }
            // lst[x+c[y]+1][y+1]={x,y} ;
            // adj[x+c[y]+1][y+1].push_back({x*101+y}) ;
        }
    }
}
// bool vvv[200003][103] ;
// void dfs2(int x,int y){
//     if (vvv[x][y]) return ;
//     vvv[x][y]=1 ;
//     for (auto xxx : adj[x][y]){
//         int a=xxx/101 ;
//         int b=xxx%101 ;
//         // cout << x << " " << y << " " << a << " " << b << endl ;
//         if (y!=b){
//             bbb[a+1]++ ;
//             bbb[x]-- ;
//             www[a]++ ;
//             www[a+1]-- ;
//             www[x]++ ;
//             www[x+1]-- ;
//         }
//         else {
//             www[a]++ ;
//             www[a+1]-- ;
//         }
//         dfs2(a,b) ;
//     }
// }
std::string solve_puzzle(std::string ss, std::vector<int> cc) {
    int i,j ;
    ss='0'+ss ;
    s=ss,c=cc ;
    n=s.size()-1 ;
    k=cc.size() ;
    for (i = 1 ; i <= n ; i ++) psw[i]=psw[i-1]+(s[i]=='_') ;
    for (i = 1 ; i <= n ; i ++) psb[i]=psb[i-1]+(s[i]=='X') ;
    dfs(0,0) ;
    // dfs2(n+1,k) ;
    // int x=n+1,y=k ;
    // string sss="" ;
    // for (i = 0 ; i < n ; i ++) sss+='_' ;
    // vector <pair<int,int>> v ;
    // while (1){
    //     auto [a,b]=lst[x][y] ;
    //     x=a,y=b ;
    //     cout << x << " " << y << endl ;
    //     v.push_back({x,y}) ;
    //     if (x==0&&y==0) break ;
    // }
    // for (i = 0 ; i < v.size()-1 ; i ++){
    //     if (v[i].second!=v[i+1].second){
    //         for (j = v[i+1].first ; j < v[i].first-1 ; j ++) sss[j]='X' ;
    //     }
    // }
    string sss="" ;
    int tt=0,tt2=0 ;
    for (i = 0 ; i <= n ; i ++){
        tt+=www[i] ;
        tt2+=bbb[i] ;
        // cout << tt << " " << tt2 << endl ;
        if (i!=0){
            // if (s[i]!='.') sss+=s[i] ;
            // else 
            if (tt&&tt2) sss+='?' ;
            else if (!tt&&!tt2) sss+='?' ;
            else if (!tt) sss+='X' ;
            else sss+='_' ;
        }
    }
    return sss;
}

컴파일 시 표준 에러 (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: 10 / 10
• Subtask 7: 10 / 10