제출 #388841

#제출 시각아이디문제언어결과실행 시간메모리
388841alireza_kavianiPaint By Numbers (IOI16_paint)C++11
90 / 100
69 ms35556 KiB
#include <bits/stdc++.h> #include "paint.h" using namespace std; #define SZ(x) int((x).size()) #define all(x) (x).begin() , (x).end() #define sep ' ' const int MAXN = 2e5 + 10; const int MAXK = 110; int n , k , dp[2][MAXK][MAXN] , mark[MAXN] , valid[MAXN]; void solve(int n , int k , string s , vector<int> c , int ind){ if(ind == 1){ reverse(all(s)); reverse(all(c)); } dp[ind][0][0] = 1; for(int i = 0 ; i <= k ; i++){ int l = 0; for(int j = 1 ; j < n ; j++){ if(s[j] == '_') l = j; if(s[j] == '_' || s[j] == '.'){ dp[ind][i][j] |= dp[ind][i][j - 1]; } if((s[j] == 'X' || s[j] == '.') && i >= 1 && j - l >= c[i - 1]){ // cout << ind << sep << i << sep << j << sep << endl; if(s[j - c[i - 1]] == 'X') continue; dp[ind][i][j] |= dp[ind][i - 1][j - c[i - 1] - 1]; } } } if(ind == 1){ for(int i = 0 ; i <= k ; i++){ reverse(dp[ind][i] , dp[ind][i] + n); } } } string solve_puzzle(string s, vector<int> c) { s = "__" + s + "__"; n = SZ(s); k = SZ(c); solve(n , k , s , c , 0); solve(n , k , s , c , 1); /* cout << n << endl; for(int i = 0 ; i <= k ; i++){ for(int j = 0 ; j < n ; j++){ cout << dp[0][i][j] << sep; } cout << endl; } for(int i = 0 ; i <= k ; i++){ for(int j = 0 ; j < n ; j++){ cout << dp[1][i][j] << sep; } cout << endl; }*/ for(int i = 0 ; i <= k ; i++){ for(int j = 2 ; j + 2 < n ; j++){ if(s[j] == 'X') continue; if(dp[0][i][j - 1] && dp[1][k - i][j + 1]){ mark[j] |= 1; } } } for(int i = 0 ; i < k ; i++){ int l = 1; fill(valid , valid + MAXN , 0); for(int j = 2 ; j + 2 < n ; j++){ if(s[j] == '_'){ l = j; continue; } if(s[j + 1] == 'X' || s[j - c[i]] == 'X') continue; if(j - l >= c[i] && dp[0][i][j - c[i] - 1] && dp[1][k - i - 1][j + 2]){ valid[j] = 1; } } int sum = 0; for(int j = n - 1 ; j >= 0 ; j--){ sum += valid[j]; if(j + c[i] < n) sum -= valid[j + c[i]]; if(sum) mark[j] |= 2; } } for(int i = 0 ; i < n ; i++){ if(s[i] == '.'){ if(mark[i] == 1) s[i] = '_'; if(mark[i] == 2) s[i] = 'X'; if(mark[i] == 3) s[i] = '?'; } } return s.substr(2 , n - 4); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...