| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 291414 | REALITYNB | Paint By Numbers (IOI16_paint) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define B 1
#define W 0
using namespace std;
int n , k ;
vector<int> b , w , p , c ;
string a ;
bool nothing(int i , int j){
int minus = 0 ;
if(i) minus=p[i-1] ;
return (minus==p[j]) ;
}
bool dp(int i , int j , int lastcolor){
if(i==n&&j==k) return 1 ;
if(i>=n) return 0 ;
bool ok =0;
if(lastcolor==B||j==k){
if(a[i]!='X') ok = dp(i+1,j,W) ;
if(ok) w[i] =1 ;
}
else{
if(a[i]!='X'){
bool okk = dp(i+1,j,W) ;
if(okk) w[i] = 1 ;
ok |=okk ;
}
if(i+c[j]<=n&¬hing(i,i+c[j]-1)){
bool okk = dp(i+c[j],j+1,W) ;
if(okk) b[i]++ , b[i+c[j]]-- ;
ok |=okk ;
//if(ok) ok&=isthere(i,)
}
}
return ok ;
}
string solve_puzzle(string aa , vector<int> cc){
a = aa ;
c= cc ;
n = a.size() ;
k=c.size() ;
b.resize(n+1);
w.resize(n+1) ;
p.resize(n+1) ;
for(int i=0;i<n;i++){
if(a[i]=='_') p[i]++ ;
if(i) p[i]+=p[i-1] ;
}
dp(0,0,W) ;
string ans ;
for(int i=0;i<n;i++){
if(i)b[i]+=b[i-1] ;
if(b[i]&w[i])ans+='?' ;
else if(b[i]) ans+='X' ;
else ans+='_' ;
}
return ans ;
}
int main(){
string ans = solve_puzzle("..........",{}) ;
cout << ans ;
}