제출 #592191

#제출 시각아이디문제언어결과실행 시간메모리
592191AlperenTPaint By Numbers (IOI16_paint)C++17
59 / 100
1 ms1364 KiB
#include <bits/stdc++.h> #include "paint.h" using namespace std; const int N = 2e5 + 5, K = 100 + 5, INF = 1e9 + 5; int n, k, forcedwhite[N], forcedblack[N], posprefix[K][N], isgood[K][N], white[N], black[N], closest[K][N]; bool pos[K][N]; void update(int arr[N], int l, int r){ arr[l]++, arr[r + 1]--; } string solve_puzzle(string s, vector<int> c) { n = s.size(), k = c.size(); s = " " + s, c.insert(c.begin(), 0); int firstx = INF; for(int i = 1; i <= n; i++){ forcedblack[i] = forcedblack[i - 1]; forcedwhite[i] = forcedwhite[i - 1]; if(s[i] == 'X'){ forcedblack[i] = i; if(firstx == INF) firstx = i; } else if(s[i] == '_') forcedwhite[i] = i; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= k; j++){ if(i - c[j] + 1 >= 1 && forcedwhite[i] < i - c[j] + 1){ if((j == 1 && i - c[j] < firstx) || ((forcedblack[i - c[j]] <= i - c[j] - 1 && posprefix[j - 1][i - c[j] - 1] - (forcedblack[i - c[j]] == 0 ? 0 : posprefix[j - 1][forcedblack[i - c[j]] - 1])))){ pos[j][i] = true; } } } for(int j = 1; j <= k; j++) posprefix[j][i] = posprefix[j][i - 1] + pos[j][i]; } for(int i = 1; i <= n; i++){ if(i < forcedblack[n]) pos[k][i] = false; else if(pos[k][i]) isgood[k][i]++, isgood[k][i - 1]--; posprefix[k][i] = posprefix[k][i - 1] + pos[k][i]; } for(int i = 1; i <= k; i++) closest[i][n + 1] = INF; for(int i = n; i >= 0; i--){ for(int j = 1; j <= k; j++){ if(pos[j][i]) closest[j][i] = i; else closest[j][i] = closest[j][i + 1]; } } for(int i = n; i >= 1; i--){ for(int j = k; j >= 1; j--){ isgood[j][i] += isgood[j][i + 1]; if(isgood[j][i] && pos[j][i]){ update(black, i - c[j] + 1, i); if(forcedblack[i - c[j]] <= i - c[j] - 1){ isgood[j - 1][i - c[j] - 1]++; if(forcedblack[i - c[j]] != 0) isgood[j - 1][forcedblack[i - c[j]] - 1]--; } isgood[j - 1][i - c[j] - 1]++; if(j == k && i < n) update(white, i + 1, n); if(j == 1 && i - c[j] >= 1) update(white, 1, i - c[1]); if(j != 1){ if(closest[j - 1][forcedblack[i - c[j]]] + 1 <= i - c[j]) update(white, closest[j - 1][forcedblack[i - c[j]]] + 1, i - c[j]); } } } } for(int i = 1; i <= n; i++) white[i] += white[i - 1]; for(int i = 1; i <= n; i++) black[i] += black[i - 1]; string ans; for(int i = 1; i <= n; i++){ if(s[i] == '.'){ if(black[i] != 0 && white[i] == 0) ans += 'X'; else if(white[i] != 0 && black[i] == 0) ans += '_'; else ans += '?'; } else ans += s[i]; } 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...