제출 #77131

#제출 시각아이디문제언어결과실행 시간메모리
77131shoemakerjoPaint By Numbers (IOI16_paint)C++14
7 / 100
2 ms812 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; #define maxn 200010 bool dp[maxn][101]; int zpref[maxn]; bool dback[maxn][101]; bool canx[maxn]; bool canblank[maxn]; int delt[maxn]; string solve_puzzle(string s, vector<int> c) { zpref[0] = 0; s = "." + s; int n = s.size()-1; int k = c.size(); c.insert(c.begin(), 0); // for (int i = 1; i <= k; i++) { // cout << "c " << i << " :: " << c[i] << endl; // } for (int i = 1; i <= n; i++) { zpref[i] = zpref[i-1]; if (s[i] == '_') zpref[i]++; } dp[0][0] = true; for (int i = 1; i <= n; i++) { if (s[i] != 'X') { for (int j = 0; j <= k; j++) { dp[i][j] |= dp[i-1][j]; } } for (int j = 1; j <= k; j++) { int prevo = i - c[j]; if (prevo < 0) continue; // cout << "prevo: " << i << " " << j << " " << prevo << endl; //guy before the rang if (zpref[i] - zpref[prevo] > 0) continue; if (s[prevo] == 'X') continue; if (j == 1) { if (prevo == 0 || dp[prevo-1][j-1]) { dp[i][j] = true; } continue; } else if (prevo == 0) continue; if (dp[prevo-1][j-1]) dp[i][j] = true; } } dback[n+1][0] = true; for (int i = n; i >= 1; i--) { if (s[i] != 'X') { for (int j = 0; j <= k; j++) { dback[i][j] |= dback[i+1][j]; } } for (int j = 1; j <= k; j++) { int afto = i + c[k+1-j]; //k+1-j is important here if (afto > n+1) continue; if (zpref[afto-1] - zpref[i-1] > 0) continue; if (s[afto] == 'X') continue; if (j == 1) { if (afto == n+1 || dback[afto+1][j-1]) { dback[i][j] = true; if (i - 2 < 0 && s[i-1] != 'X' && j == k || dp[i-2][k-j] && s[i-1] != 'X') { // cout << i << " to " << afto << endl; delt[i]++; delt[afto]--; } } continue; } else if (afto == n+1) continue; if (dback[afto+1][j-1]) { dback[i][j] = true; if (i - 2 < 0 && s[i-1] != 'X' && j == k || dp[i-1][k-j]) { // cout << i << "to :: " << afto << endl; delt[i]++; delt[afto]--; } } } } int crun = 0; for (int i = 1; i <= n; i++) { // if (s[i] != '.') continue; crun += delt[i]; if (crun) canx[i] = true; for (int j = 0; j <= k; j++) { if (dp[i-1][j] && dback[i+1][k-j]) { // cout << "WE MADE IT" << endl; canblank[i] = true; } } } string ans; for (int i = 1; i <= n; i++) { // cout << i << " " << canx[i] << " " << canblank[i] << endl; if (s[i] != '.') ans += s[i]; else { if (canx[i] && canblank[i]) ans += '?'; else if (canx[i]) ans += 'X'; else ans += '_'; } } // for (int i = 1; i <= n; i++) { // for (int j = 0; j <= k; j++) { // cout << i << " " << j << " : " << dp[i][j] << endl; // } // } return ans; }

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

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:76:7: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
      if (i - 2 < 0 && s[i-1] != 'X'
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~
       && j == k || 
       ^~~~~~~~~
paint.cpp:89:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (i - 2 < 0 && s[i-1] != 'X' && 
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
      j == k || dp[i-1][k-j]) {
      ~~~~~~
#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...