제출 #137401

#제출 시각아이디문제언어결과실행 시간메모리
137401mirbek01Paint By Numbers (IOI16_paint)C++11
59 / 100
4 ms1272 KiB
#include "paint.h" //#include "grader.cpp" #include <cstdlib> #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 3; int n, m; int pf[3][N], dp[2][202][N], pfX[N], sfX[N], f[202][N]; int get(int l, int r, int tp){ if(l > r) return 0; return pf[tp][r] - pf[tp][l - 1]; } int Get(int l, int r, int tp){ if(l > r) return 0; return f[tp][r] - f[tp][l - 1]; } string solve_puzzle(string s, vector<int> c) { n = (int)s.size(); m = (int)c.size(); s = ' ' + s; for(int i = 1; i <= n; i ++){ if(s[i] == 'X') pf[0][i] ++, pfX[i] = i; else pfX[i] = pfX[i - 1]; if(s[i] == '_') pf[1][i] ++; if(s[i] == '.') pf[2][i] ++; pf[0][i] += pf[0][i - 1]; pf[1][i] += pf[1][i - 1]; pf[2][i] += pf[2][i - 1]; } sfX[n + 1] = n + 1; for(int i = n; i >= 1; i --){ if(s[i] == 'X') sfX[i] = i; else sfX[i] = sfX[i + 1]; } for(int i = c[0]; i <= n; i ++) if(get(i - c[0] + 1, i, 1) == 0 && get(1, i - c[0], 0) == 0) dp[0][0][i] = 1; for(int i = 1; i < m; i ++){ vector <int> pf(n + 1, 0); for(int j = 1; j <= n; j ++) pf[j] = pf[j - 1] + dp[0][i - 1][j]; for(int j = c[i] + 1; j <= n; j ++){ if(s[j - c[i]] == 'X') continue; if(get(j - c[i] + 1, j, 1) > 0) continue; int sum = pf[j - c[i] - 1] - pf[ max(0, pfX[ j - c[i] - 1 ] - 1) ]; if(sum <= 0) continue; dp[0][i][j] = 1; } } for(int i = n; i >= c[m - 1]; i --){ if(get(i - c[m - 1] + 1, i, 1) == 0 && get(i + 1, n, 0) == 0) dp[1][m - 1][i] = 1; } for(int i = m - 2; i >= 0; i --){ vector <int> sf(n + 2, 0); for(int j = n; j >= 1; j --) sf[j] = sf[j + 1] + dp[1][i + 1][j]; for(int j = c[i]; j <= n; j ++){ if(s[j + 1] == 'X') continue; if(get(j - c[i] + 1, j, 1) > 0) continue; if(j + c[i + 1] + 1 > n) continue; int sum = sf[j + c[i + 1] + 1] - sf[ min(sfX[j + 1] + c[i + 1] + 1, n + 1) ]; if(sum <= 0) continue; dp[1][i][j] = 1; } } for(int i = 0; i < m; i ++) for(int j = 1; j <= n; j ++) if(dp[0][i][j] && !dp[1][i][j]) dp[0][i][j] = 0; for(int i = 0; i < m; i ++) for(int j = 1; j <= n; j ++) f[i][j] = f[i][j - 1] + dp[0][i][j]; /* for(int i = 0; i < m; i ++){ for(int j = 1; j <= n; j ++){ cout << dp[0][i][j] << " "; } cout << endl; } */ string ans; for(int i = 1; i <= n; i ++){ if(s[i] != '.'){ ans += s[i]; continue; } int canX = 0, can_ = 0; for(int j = 0; j < m; j ++){ if(j == 0){ if(get(1, i - 1, 0) == 0 && i + c[j] <= n && Get(i + c[j], min(sfX[i + 1] + c[j], n), j)) can_ = 1; } else { if(Get(max(pfX[i - 1], 1), i - 1, j - 1) && i + c[j] <= n && Get(i + c[j], min(sfX[i + 1] + c[j], n), j)) can_ = 1; } if(Get(i, min(i + c[j] - 1, n), j)) canX = 1; // cout << i << " -- " << can_ << endl; } if(Get(pfX[i - 1], i - 1, m - 1) && get(i + 1, n, 0) == 0) can_ = 1; if(can_ && canX) ans += '?'; else if(can_) ans += '_'; else ans += 'X'; } return ans; }
#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...