제출 #69139

#제출 시각아이디문제언어결과실행 시간메모리
69139NavickPaint By Numbers (IOI16_paint)C++17
59 / 100
5 ms888 KiB
#include <bits/stdc++.h> #include <cstdlib> #include "paint.h" #define F first #define S second #define pii pair<int, int> #define pb push_back using namespace std; const int maxN = 1e5 + 10, maxK = 102; bool wh[maxN], bl[maxN], dp[maxN][maxK], pd[maxN][maxK], sh[maxN][maxK]; int ps[maxN], sum[maxK][maxN], ps2[maxN]; std::string solve_puzzle(std::string s, std::vector<int> c) { int n = s.size(), k = c.size(); for (int i=0; i<n; i++) { ps[i + 1] = ps[i] + (s[i] == '_'); ps2[i + 1] = ps2[i] + (s[i] == 'X'); } dp[0][0] = 1; for (int i=1; i<=n; i++) for (int j=0; j<=k; j++) { if(j == 0) { dp[i][j] = (ps2[i] == 0); continue ; } if(s[i - 1] == '_' || s[i - 1] == '.') dp[i][j] = dp[i - 1][j]; if((s[i - 1] == 'X' || s[i - 1] == '.') && i >= c[j - 1]) { int td = ps[i] - ps[i - c[j - 1]]; if(td == 0 && (i - c[j - 1] - 1 < 0 || s[i - c[j - 1] - 1] != 'X')) { dp[i][j] |= dp[max(0, i - c[j - 1] - 1)][j - 1]; sh[i][j] = dp[max(0, i - c[j - 1] - 1)][j - 1]; } } //cout << i << ',' << j << " --> " << sh[i][j] << endl; } pd[n][k] = 1; for (int i=n-1; i>=0; i--) for (int j=k; j>=0; j--) { if(j == k) { pd[i][j] = (ps2[n] - ps2[i] == 0); continue ; } if(s[i] == '_' || s[i] == '.') pd[i][j] = pd[i + 1][j]; if((s[i] == 'X' || s[i] == '.') && n - i >= c[j]) { int td = ps[i + c[j]] - ps[i]; if(td == 0 && (i + c[j] >= n || s[i + c[j]] != 'X')) pd[i][j] |= pd[min(n, i + c[j] + 1)][j + 1]; } } for (int i=0; i<n; i++) { if(s[i] == '.') { for (int j=0; j<=k; j++) wh[i] |= (dp[i][j] && pd[i + 1][j]); //cout << i << " --> " << wh[i] << endl; } } for (int i=1; i<=n; i++) for (int j=1; j<=k; j++) { sum[j][i] = sum[j][i - 1]; if(!sh[i][j]) continue ; if(i >= n || (s[i] != 'X')) sh[i][j] = pd[min(n, i + 1)][j]; //cout << i << ',' << j << " --> " << sh[i][j] << endl; sum[j][i] += sh[i][j]; } for (int i=0; i<n; i++) { if(s[i] != '.') continue ; for (int j=1; j<=k; j++) { int td = sum[j][min(n, i + c[j - 1])] - sum[j][i]; if(td) bl[i] = true; } //cout << i << " <>>> " << bl[i] << endl; } for (int i=0; i<n; i++) { if(s[i] == '.') if(wh[i] && bl[i]) s[i] = '?'; else if(wh[i]) s[i] = '_'; else if(bl[i]) s[i] = 'X'; } return s; }

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

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:108:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   if(s[i] == '.')
     ^
#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...