제출 #1021851

#제출 시각아이디문제언어결과실행 시간메모리
1021851vjudge1Paint By Numbers (IOI16_paint)C++17
90 / 100
7 ms7004 KiB
#include <bits/stdc++.h> #define ent '\n' typedef long long ll; using namespace std; const int maxn = 2e5+12; int suff[maxn][103]; int pref[maxn][103]; int can[maxn]; int prefw[maxn]; int prefb[maxn]; int c[maxn]; int n, k; string solve_puzzle(string s, vector<int> C){ n = s.size(), k = C.size(); for(int i=0;i<n;i++){ prefw[i+1] = prefw[i] + (s[i] == '_'); prefb[i+1] = prefb[i] + (s[i] == 'X'); c[i+1] = C[i]; } string ans = ""; pref[0][0] = 1; for(int i=1;i<=n;i++){ for(int j=0;j<=k;j++){ if(s[i-1] != 'X') pref[i][j] = pref[i-1][j]; if(j > 1 && i > c[j] && pref[i-c[j]-1][j-1] && prefw[i] == prefw[i-c[j]] && s[i - c[j] - 1] != 'X') { pref[i][j] = 1; } if(j == 1 && i >= c[j] && pref[i-c[j]][j-1] && prefw[i] == prefw[i-c[j]]){ pref[i][j] = 1; } } } suff[n+1][k+1] = 1; for(int i=n;i;i--){ for(int j=k+1;j>0;j--){ if(s[i-1] != 'X') suff[i][j] = suff[i+1][j]; if(j < k && n - i + 1 > c[j] && suff[i+c[j]+1][j+1] && prefw[i+c[j]-1] == prefw[i-1] && s[i + c[j] - 1] != 'X'){ suff[i][j] = 1; } if(j == k && n - i + 1 >= c[j] && suff[i+c[j]][j+1] && prefw[i+c[j]-1] == prefw[i-1]){ suff[i][j] = 1; } } } for(int j=1;j<=k;j++){ for(int l=1;l+c[j]-1<=n;l++){ int r = l + c[j] - 1; if(prefw[r] - prefw[l-1] == 0 && r + (j != k) <= n && l - 1 - (j != 1) >= 0 && pref[l - 1 - (j != 1)][j-1] && suff[r + 1 + (j != k)][j+1] && (l == 1 || l > 1 && s[l-2] != 'X') && (r == n || r < n && s[r] != 'X')) { can[l]++, can[r+1]--; } } } for(int i=1;i<=n;i++){ can[i] += can[i-1]; bool ok = 0, fg = 0; for(int j=0;j<=k;j++){ if(pref[i-1][j] && suff[i+1][j+1] && s[i-1] != 'X'){ fg = 1; } } if(!fg){ ans += 'X'; } else if(!can[i]){ ans += '_'; } else{ ans += '?'; } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:53:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   53 |                (l == 1 || l > 1 && s[l-2] != 'X') && (r == n || r < n && s[r] != 'X'))
      |                           ~~~~~~^~~~~~~~~~~~~~~~
paint.cpp:53:71: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   53 |                (l == 1 || l > 1 && s[l-2] != 'X') && (r == n || r < n && s[r] != 'X'))
      |                                                                 ~~~~~~^~~~~~~~~~~~~~
paint.cpp:61:14: warning: unused variable 'ok' [-Wunused-variable]
   61 |         bool ok = 0, fg = 0;
      |              ^~
#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...